c++实现数组、字符串中的元素序列全排列_c++字符串全排列

• 小技巧：
  • 实现数组、字符串中的元素全排列组合
    • 实现思路：序列的全排列，就是从其中顺序调出一个元素作为第一个元素，将剩余的元素做全排列。也就是把第一个元素，和后续每个元素做一次交换，把第一个元素以后的序列做全排列。全排列的结果和第一个元素合起来就是全排列的结果。其实就是递归。

class Solution{
    public:
        int combination(string str){
            int num=0;
            int n =str.size();
            string strLen;
            dfs(str,strLen,n,num,0);
            return num;
        };
        void dfs(string&str,string&strLen,const int&n,const int&index){
            if(index==n){
                cout<<strLen<<endl;
                 num++;
                return ;
            }
            for (size_t i = index; i < n; i++)
            {
                strLen+=str[i];
                swap(str[index],str[i]);
                dfs(str,strLen,n,index+1);
                strLen.erase(strLen.end()-1);
                swap(str[index],str[i]);
            }
        }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 说明：每个循环中有两个swap。第一个表示把子序列的头元素依次跟第i个元素交换；然后生成子序列（walkIndex后的序列）的全排列；然后恢复（再一次调用swap）.
  必须恢复，是因为思路是“顺序调出每一个元素作为第一个元素”，如果子序列的全排列结束后不恢复，那下一次for循环就拿不到正确的元素了。比如原始序列为
  1 2 3 4，最外层遍历先把1和1交换（相当于没交换），得到子序列2 3 4的全排列，和1组成 6 组结果；
  然后应该把1和2交换，2在第一个元素位置，子序列是 1 3 4，在计算这个子序列的全排列，和2
  组成6组结果；这时必须恢复1和2原来的顺序，才能让1和3交换做下一次的排序，也就是计算子序列 1 3
  4后，必须再一次swap恢复出厂设置。