一、深搜法
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;
string str;
bool mark[100];
int ans[100];
void DFS(int pos, int num)
{
if(num == str.length())
{
for(int i = 0; i < num; ++i)
cout << str[ans[i]];
cout << endl;
return;
}
for(int i = 0; i < str.length(); ++i)
{
if(mark[i] == true)
continue;
mark[i] = true;
ans[num] = i;
DFS(i, num+1);
mark[i] = false;
}
}
int main()
{
ifstream cin("in.txt");
while(getline(cin, str))
{
sort(str.begin(), str.end());
for(int i = 0; i < str.length(); ++i)
{
for(int j = 0; j < str.length(); ++j)
{
ans[j] = 0;
mark[j] = false;
}
mark[i] = true;
ans[0] = i;
DFS(i, 1);
}
}
return 0;
}
二、递归法
对于包含重复字符的字符串的全排列，在使用递归法交换两个元素之前，需要判断是否需要交换。在from到to位置的元素中，如果存在与str[j]相同的元素，则不必交换
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;
string str;
bool isSwap(int start, int pos)
{
for(int i = start; i < pos; ++i)
if(str[i] == str[pos])
return false;
return true;
}
void CalcAllPermutation(string & str, int from, int to)
{
if(to <= 1)
return;
if(from == to)
cout << str << endl;
else
{
for(int i = from; i <= to; ++i)
{
if(isSwap(from, i))
{
swap(str[i], str[from]);
CalcAllPermutation(str, from+1, to);
swap(str[i], str[from]); //回溯
}
}
}
}
int main()
{
ifstream cin("in.txt");
while(getline(cin, str))
{
sort(str.begin(), str.end());
CalcAllPermutation(str, 0, str.length()-1);
}
return 0;
}
三、STL next_permutation
获取字典序的下一次全排列：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[4] = {1, 2, 3, 4};
next_permutation(a, a+4);
//向后获取字典序的下一次全排列
for(int i = 0; i < 4; ++i)
cout << a[i] << " ";
cout << endl;
//向前获取字典序的上一次全排列
prev_permutation(a, a+4);
for(int i = 0; i < 4; ++i)
cout << a[i] << " ";
cout << endl;
//获取所有全排列
do{
for(int i = 0; i < 4; ++i)
cout << a[i] << " ";
cout << endl;
}while(next_permutation(a, a+4));
return 0;
}
四、非递归法（即STL next_permutation 函数的实现）
使用非递归法，要求我们实现的函数具有这样的功能：对于任一序列可以按照字典序计算出下一序列。如：21543的下一序列是23145，分四步：
- 从最右边开始比较两两相邻的元素，知道找到第一个升序的元素对，并记录元素对左边的元素a[i]，当i<0时，结束（上例中找到的元素为1）
- 从最右边开始找到第一个比a[i]大的元素a[k]（找到3）
- 交换a[i]和a[j]（交换1和3）
- 把从i+1位到最后的元素翻转
#include <iostream>
#include <algorithm>
using namespace std;
bool calNextPermutation(int * a, int n)
{
//第一步
for(int i = n-2; i >= 0 && a[i] > a[i+1]; --i)
{
;
}
if(i < 0)
return false;
//第二步
for(int k = n-1; k > i && a[k] <= a[i]; --k)
{
;
}
//第三步
swap(a[i], a[k]);
//第四步
reverse(a+k+1, a+n);
return true;
}
int main()
{
int a[4] = {1, 2, 3, 4};
//向后获取最近的一次全排列
if(calNextPermutation(a, 4))
{
for(int i = 0; i < 4; ++i)
cout << a[i] << " ";
cout << endl;
}
}
五、全排列的应用—八皇后问题
题意：在8X8的国际象棋棋盘上摆放8个皇后，彼此之间不能相互攻击。即：8个皇后任意两个不能处于同一行、同一列、同一对角线。
算法思想：使用maze[i] = j 表示第i行的皇后所在的列j,数组使用1-8初始化，递归求得数组元素的全排列，由于所有的皇后均不在同一行、同一列，所以，我们只需判断任意两个皇后是否在同一对角线上即可。
#include <iostream>
#include <algorithm>
using namespace std;
int maze[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
int len;
int cnt = 0;
bool check()
{
for(int i = 1; i <= len; ++i)
for(int j = i + 1; j <= len; ++j)
{
if(i-j == maze[i]-maze[j] || j-i == maze[i]-maze[j])
return false;
}
return true;
}
void calPermutation(int * maze, int start)
{
if(start == len)
{
if(check())
{
cnt++;
for(int i = 1; i <= len; ++i)
cout << maze[i];
cout << endl;
}
}
else
{
for(int i = start; i <= len; ++i)
{
swap(maze[start], maze[i]);
calPermutation(maze, start+1);
swap(maze[start], maze[i]);
}
}
}
int main()
{
len = sizeof(maze)/sizeof(int)-1;
calPermutation(maze, 1);
cout << cnt << endl;
return 0;
}
