全排列

一、全排列的递归实现（不考虑去重）

从第一个数字起，每个数分别与它后面的数字交换。

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 //全排列的递归实现（不考虑去重）
 8 //k表示当前选取到第几个数,m表示共有多少数
 9 void AllRange(string pszStr, int k, int m)
10 {
11     if (k == m)
12     {
13         static int num = 1;
14         cout << "第" << num++ << "个排列" << " : " << pszStr << endl;
15     }
16     else
17     {
18         for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
19         {
20             swap(pszStr[k], pszStr[i]);
21             cout <<"swap1: " << pszStr << endl;
22             AllRange(pszStr, k + 1, m);
23             swap(pszStr[k], pszStr[i]);
24             cout <<"swap2: " << pszStr << endl;
25         }
26     }
27 }
28 void Foo(string pszStr)
29 {
30     AllRange(pszStr, 0, pszStr.length() - 1);
31 }
32 int main()
33 {
34     string szTextStr = "123";
35     cout << "全排列的递归实现:" << endl;
36     cout << szTextStr << "的全排列如下:" << endl;
37     Foo(szTextStr);
38     return 0;
39 }

全排列的递归实现:
123的全排列如下:
swap1: 123
swap1: 123
第1个排列 : 123
swap2: 123
swap1: 132
第2个排列 : 132
swap2: 123
swap2: 123
swap1: 213
swap1: 213
第3个排列 : 213
swap2: 213
swap1: 231
第4个排列 : 231
swap2: 213
swap2: 123
swap1: 321
swap1: 321
第5个排列 : 321
swap2: 321
swap1: 312
第6个排列 : 312
swap2: 321
swap2: 123

二、全排列的递归实现（考虑去重）

从第一个数字起每个数分别与它后面非重复出现的数字交换。第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 //[begin,end)中是否有数字与下标为end的数字相等
 8 bool IsSwap(string s, int begin, int end)
 9 {
10     for (int i = begin;i < end;i++)
11         if (s[i] == s[end])
12             return false;
13     return true;
14 }
15 
16 //全排列的递归实现（考虑去重）
17 //k表示当前选取到第几个数,m表示共有多少数
18 void AllRange(string pszStr, int k, int m)
19 {
20     if (k == m)
21     {
22         static int num = 1;
23         cout << "第" << num++ << "个排列" << " : " << pszStr << endl;
24     }
25     else
26     {
27         for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
28         {
29             if(IsSwap(pszStr,k,i))
30             {
31                 swap(pszStr[k], pszStr[i]);
32                 cout << "swap1: " << pszStr << endl;
33                 AllRange(pszStr, k + 1, m);
34                 swap(pszStr[k], pszStr[i]);
35                 cout << "swap2: " << pszStr << endl;
36             }
37         }
38     }
39 }
40 
41 void Foo(string pszStr)
42 {
43     AllRange(pszStr, 0, pszStr.length() - 1);
44 }
45 
46 int main()
47 {
48     string szTextStr = "122";
49     cout << "全排列的递归实现:" << endl;
50     cout << szTextStr << "的全排列如下:" << endl;
51     Foo(szTextStr);
52     return 0;
53 }

全排列的递归实现:
122的全排列如下:
swap1: 122
swap1: 122
第1个排列 : 122
swap2: 122
swap2: 122
swap1: 212
swap1: 212
第2个排列 : 212
swap2: 212
swap1: 221
第3个排列 : 221
swap2: 212
swap2: 122