算法系列的博客是我准备实习面试时进行的总结，解决问题的同时，还会包括一些易遗忘的知识，最近会持续更新，其中字符串是第一部分，里面的内容都是基于个人的学习和理解，有不足之处欢迎指正。
字符串的全排列是字符串类的算法题的一个考察点，属于普通问题，它有两种实现方法，递归算法和非递归算法，非递归的方法要稍微难一点，以下会依次进行介绍。
全排列的递归算法
算法思想：求n位的字符串的全排列，先确定第0位，然后对后面n-1位进行全排列，在对n-1为进行全排列时，先确定第1位，然后对后面的n-2位进行全排列...由此得到递归函数和递归的结束条件。全排列也就是交换位置，到n-2位时，就是将n-2和n-1交换位置。
例子：abc，第一位是a固定，对后面的bc交换位置得abc,acb.
当a和b交换位置之后，得到bac，对ac进行全排列bac,bca.
当a和c交换位置之后，得到cba，对ba进行全排列得cba,cab.
根据以上思想编写代码：
1.使用宏定义来实现两个字符交换位置（或者自定义一个交换的函数）
注意：如果是宏定义接收的参数是字符类型，直接交换位置，因为宏在引用时，相当于直接把宏展开插入代码中，如果是函数，接收的参数是指针类型。
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t))
main函数，定义一个字符串，需要注意的c语言里没有字符串，所以只能由字符数组表示字符串。
char list[] = "abc";
perm(list, 0, strlen(list)-1);
system("pause");
2.定义全排列的递归函数perm(char *list, int i, int n)
int j, temp;
if (i == n) {//n表示字符串最后一位的下标
printf("\t%s\n", list);
}
else {
for (j = i; j <= n; j++){
//使用宏定义，传的是数值，如果这的swap用函数实现，传的应该是指针
SWAP(list[i], list[j], temp);
//交换位置后，输出以list[j]不变，后面的字母改变的所有排列
perm(list, i + 1, n);
SWAP(list[i], list[j], temp);
}
}
结果：
abc的全排列
但是以上算法会出现一个问题，比如字符串为abb，结果会出错：
abb的全排列
很明显以上的结果是不对的，如何改进呢？
字符串全排列递归算法的改进
出现以上问题的原因，主要是因为相同的字符进行了多次交换。举个栗子abb,a固定时，后面的字符位置不变，得到abb，当第2个b和第3个b交换时，又得到了abb，解决这个问题的思路在于，在交换时进行判断，如果后面的字符有重复就不交换。当第i个字符和第j个字符交换位置时，判断范围是[i,j)是否有和j重复的数，代码如下：
判断是否交换的函数：
bool isSwap(char *list, int begin, int end) {
for (int i = begin; i < end; i++){
if (list[i] == list[end])
return false;
}
return true;
}
改进perm函数：
void perm(char *list, int i, int n){
int j, temp;
if (i == n) {
printf("\t%s\n", list);
}
else {
for (j = i; j <= n; j++){
if (isSwap(list, i, j)) {
//使用宏定义，传的是数值，如果这的swap用函数实现，传的应该是指针
SWAP(list[i], list[j], temp);
//交互位置后，输出以list[j]不变，后面的字母改变的所有排列
perm(list, i + 1, n);
SWAP(list[i], list[j], temp);
}
}
}
}
结果：
abb的全排列
字符串全排列非递归算法
首先介绍一个知识点，替换点和替换数。假设有字符串“13421“，我们从字符串的最后一位开始扫描，找到第一对递减的字符，在这个例子中，12不是，24不是，43就是了，其中3就是替换数，替换数的位置就是替换点。
算法思想：先找到替换点，然后从最后一位开始扫描，找到比替换数大的最小的数【注意必须是最小的】，交换两个的位置，然后将替换点后面的数进行逆序，如"421"就逆序成"124"。如此循环，得到全排列。
注意：在实现时我们可以先对原来的字符串进行排序，这里使用的是VC库中的快排函数qsort(),先对字符串进行排序的好处在于，找比替换数大的最小的数时处理很方便，因为升序排序之后，比替换点大的最小的数就是距离替换点最近的数，代码中体现在while (pFind <= *p)
--pFind;
代码如下：
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t))
/*反转函数*/
void reverse(char *a, char *b){
int t = 0;
/*比较的是下标，不是字符数据的值*/
while (a < b){
SWAP(*a, *b, t);
a++;
b--;
}
}
/*计算下一个排列*/
bool nextPermutation(char list[]){
/*从字符串的最后一位开始向前扫描*/
char *pEnd = list + strlen(list)-1;
if (list == pEnd)
return false;
char *p, *q, *pFind;//p指向字符串的前一位，q指向字符串的后一位
p = pEnd;
while (p != list) {
q = p;
--p;
if (*p < *q){/*找降序的两个数，即后一个大于前一个，前一个是替换点*/
/*从后面找比替换数p大的最小的数*/
pFind = pEnd;
while (*pFind <= *p)
--pFind;
//替换
int t = 0;
SWAP(*pFind, *p, t);
/*替换点之后的数反转*/
reverse(q, pEnd);
return true;
}
}
reverse(p, pEnd);/*如果没有下一个排列，全部反转*/
return false;
}
int qSortCmp(const void *pa, const void *pb){
return *(char*)pa - *(char*)pb;
}
int main(void) {
char list[] = "abc";
/*先对字符串进行快速排序*/
qsort(list, strlen(list), sizeof(list[0]),qSortCmp);
int i = 1;
do{
printf("\t%s\n",list);
} while (nextPermutation(list));
system("pause");
return 0;
}
结果：
非递归-abc的全排列
非递归-abb的全排列
网友评论