算法-字符串之全排列

  算法系列的博客是我准备实习面试时进行的总结，解决问题的同时，还会包括一些易遗忘的知识，最近会持续更新，其中字符串是第一部分，里面的内容都是基于个人的学习和理解，有不足之处欢迎指正。

字符串的全排列是字符串类的算法题的一个考察点，属于普通问题，它有两种实现方法，递归算法和非递归算法，非递归的方法要稍微难一点，以下会依次进行介绍。

全排列的递归算法

算法思想：求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的全排列