题目
输入一个字符串，打印出该字符串中字符的所有排列。
例如，输入字符串abc，则打印出由字符串a、b、c能排列出的所有字符串abc、acb、bac、bca、cab、cba。
思路
求整个字符串的排列，可以看成两步。
第一步求所有可能出现在第一个位置的字符，即把第一个字符和后面的所有字符交换。下图（a）就是分别把第一个字符a和后面的b、c等字符交换的情形。
第二步固定第一个字符，求后面所有字符的排列
这时我们仍然把后面的所有字符分成两部分：后面的字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换如下图（b）
20190112115317413.png
下图很好的解释了过程
4010043-5ce367990c7d8ccf.png
代码实现
#include <iostream>
using namespace std;
void Permutation(char *pStr, char *pBegin);
void Permutation(char *pStr) {
if (pStr == nullptr)
return;
Permutation(pStr, pStr);
}
void Permutation(char *pStr, char *pBegin) {
if (*pBegin == '\0') { // 字符串结束打印字符串
printf("%s\n", pStr);
} else {
// 遍历整个字符串
for (char *pCh = pBegin; *pCh != '\0'; ++pCh) {
// 交换当前字符与首字符
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
}
pStr指向整个字符串，pBegin指向当前排列字符串的第一个字符。在每一次递归的时候，从pBegin向后扫描每一个字符（指针pCh指向的字符）。在交换pBegin和pCh指向的字符之后，再对pBegin后面的字符串递归地进行排列操作，直至pBegin指向字符串末尾
测试部分
void Test(char* pStr) {
if(pStr == nullptr)
printf("Test for nullptr begins:\n");
else
printf("Test for %s begins:\n", pStr);
Permutation(pStr);
printf("\n");
}
int main(int argc, const char * argv[]) {
Test(nullptr);
char string1[] = "";
Test(string1);
char string2[] = "a";
Test(string2);
char string3[] = "ab";
Test(string3);
char string4[] = "abc";
Test(string4);
return 0;
}
运行输出
Test for nullptr begins:
Test for begins:
Test for a begins:
a
Test for ab begins:
ab
ba
Test for abc begins:
abc
acb
bac
bca
cba
cab
上面是实现了功能，但是如果字符串中存在相同的字符，那么应该如何处理去重呢？
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字进行交换
//在[from, to]区间中是否有字符与下标为from的字符相等
bool IsSwap(char *from, char *to) {
char* p;
for(p = from; p < to; p++) {
if(*p == *to)
return false;
}
return true;
}
void Permutation(char *pStr, char *pBegin) {
if (*pBegin == '\0') { // 字符串结束打印字符串
printf("%s\n", pStr);
} else {
// 遍历整个字符串
for (char *pCh = pBegin; *pCh != '\0'; ++pCh) {
if (IsSwap(pBegin, pCh)) {
swap(*pCh, *pBegin);
Permutation(pStr, pBegin + 1);
swap(*pCh, *pBegin);
}
}
}
}
参考
《剑指offer》
