全排列算法总结

本文同时发布在我的个人博客：https://wiki.hushhw.cn/posts/83505976.html

全排列递归算法

算法思想

求 n 位的字符串的全排列，先确定第 0 位，然后对后面 n-1 位进行全排列，在对 n-1 为进行全排列时，先确定第 1 位，然后对后面的 n-2 位进行全排列…由此得到递归函数和递归的结束条件。全排列也就是交换位置，到 n-2 位时，就是将 n-2 和 n-1 交换位置。

例如输入字符串abc，则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba 。具体过程如下：

• 第一位是 a 固定，对后面的 bc 交换位置得 abc，acb；
• 当 a 和 b 交换位置之后，得到 bac，对 ac 进行全排列 bac，bca；
• 当 a 和 c 交换位置之后，得到 cba，对 ba 进行全排列得cba，cab。

实现

于是我们根据这种思想写出第一个版本的算法：

 void perm(char *list, int i, int n){      int j, temp;   if (i == n) {//n表示字符串最后一位的下标     printf("%s\n", list);   } else {     for (j = i; j <= n; j++){         swap(list[i], list[j], temp);         //交换位置后，输出以list[j]不变，后面的字母改变的所有排列         perm(list, i + 1, n);         swap(list[i], list[j], temp);     }   }  }

这样我们实现基本的全排列的功能，但是这样我们并不能解决一种情况，即类似于abb去重的问题，abb这种交换后一样的情况在输出时会输出两个，于是我们需要对我们的算法进行改进，得到第二版的算法：

 bool isSwap(char *list, int begin, int end) {      for (int i = begin; i < end; i++){          if (list[i] == list[end])              return false;     }      return true;  }  ​  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(list[i], list[j], temp);                  //交互位置后，输出以list[j]不变，后面的字母改变的所有排列                  perm(list, i + 1, n);                  swap(list[i], list[j], temp);             }             }     }  }

我们在进行交换前进行判断，当第 i 个字符和第 j 个字符交换位置时，判断范围是 [i, j) 是否有和 j 重复的数，如果重复我们跳过这种情况。

例题

题目内容：对字符串（数字，字母，符号）进行全排列，并统计全排列的种树

输入描述：输入一个字符串

输出描述：输出字符串的全排列，每种情况占一行，最后一行输出全排列的个数

输入样例

123

输出样例

123 132 213 231 312 321 6

这题目的坑在于对输出的全排列需要排序，ac代码如下：

 #include <cstdio>    #include <cstring>    #include <algorithm>  #include <iostream>    using namespace std;    int sum=0;    string s[105];  string str;      void swap(int a,int b) {        char temp;   temp = str[a];   str[a] = str[b];   str[b] = temp;    }        bool isSwap(int k, int m) {        for(int i=k;i<m;i++)        if(str[m]==str[i])            return false;        return true;    }        void Perm(int k, int m) {        if(k==m){           // cout<<s<<endl;            s[sum++] = str;     } else {            for(int i=k;i<=m;i++){                if(isSwap(k,i)){                    swap(k,i);                    Perm(k+1,m);                    swap(k,i);               }             }       }    }        int main(){        while(cin>>str){            sum=0;            int len=str.length();            Perm(0,len-1);          sort(s,s+sum);   for(int i=0;i<sum;i++)   cout<<s[i]<<endl;          cout<<sum<<endl;           }        return 0;    }  

使用next_permutation（排列组合）函数

使用

对于next_permutation函数，其函数原型为：

 #include <algorithm>  bool next_permutation(iterator start,iterator end)

当当前序列不存在下一个排列时，函数返回 false，否则返回 true。

例如这个例子：

 #include <iostream>    #include <algorithm>    using namespace std;    int main()    {        int num[3]={1,2,3};        do       {            cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;       }while(next_permutation(num,num+3));        return 0;    }  

输出的结果为：

 1 2 3  1 3 2  2 1 3  2 3 1  3 1 2  3 2 1

当把 while(next_permutation(num,num+3)) 中的 3 改为 2 时，输出就变为了：

 1 2 3  2 1 3

由此可以看出，next_permutation(num,num+n) 函数是对数组 num 中的前 n 个元素进行全排列，同时并改变num数组的值。

另外，需要强调的是，next_permutation() 在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。比如，如果数组 num 初始化为 2，3，1，那么输出就变为了：

 2 3 1  3 1 2  3 2 1

next_permutation() 函数功能是输出所有比当前排列大的排列，顺序是从小到大。

prev_permutation() 函数功能是输出所有比当前排列小的排列，顺序是从大到小。

此外，next_permutation(node, node+n, cmp) 可以对结构体 num 按照自定义的排序方式 cmp 进行排序。

举例

经典的24点问题就可以用全排列来暴力解决，北邮复试机考就考到了这个题。

本文参考自：

C++STL中全排列函数next_permutation的使用