全排列的定义见全排列.
这里我们详细讲一下交换法和字典序法
交换法
举个简单的例子，假设我们要对1234进行全排列
1.首先保证1不变，对234进行全排列
同样的，对234进行全排列可以保证2不变，对34进行全排列，然后保证3不变，对4进行全排列，因为4只有一个数，所以全排列只有一种，然后我们就得到了
1234
1243
1324
1342
1423
1243
2.这样我们就得到了以1开头的所有全排列，接下来就是得到分别以2，3，4开头的全排列了
只要我们将1与2，3，4分别交换，就分别得到了以2，3，4开头的初始序列。
代码
#include<iostream>
using namespace std;
int arr[5]={0,1,2,3,4};
void swap(int x,int y)//用于交换数组的两个数
{
int temp=arr[x];
arr[x]=arr[y];
arr[y]=temp;
}
int resove(int n)//递归函数
{
if(n==5)//当尝试对不存在的数组元素进行递归时，标明所有数已经排列完成，输出。
{
for(int i=0;i<5;i++)
cout<<arr[i];
cout<<endl;
return 0;
}
for(int i=n;i<5;i++)//循环实现交换和之后的全排列
{//i是从n开始 i=n;swap(n,i)相当于固定当前位置，在进行下一位的排列。
swap(n,i);
resove(n+1);
swap(n,i);
}
}
int main()
{
resove(0);
}
如果初始序列中有重复元素的话，只要去重就可以了
bool isSwap(int begin,int end)
{
for(int i=begin;i<end;i++)
{
if(arr[i]==arr[end])
return false;
return true;
}
}
然后在循环的时候加上这个条件就行了。
for(int i=n;i<5;i++)//循环实现交换和之后的全排列
{//i是从n开始 i=n;swap(n,i)相当于固定当前位置，在进行下一位的排列。
if(isSwap(n,i))
{
swap(n,i);
resove(n+1);
swap(n,i);
}
}
123的全排列
123
132
213
231
321
312
可能你已经发现了，这样的输出是没有顺序的，如果我们要求输出必须按照字典序输出的话，这样显然是不可以的。所以接下来介绍一种字典序法。
字典序法
直接看代码吧，我也不知道咋解释
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 7;
char site[maxn] = {0};
string str;
void solve(int num)
{
if(num == str.length())
{
for(int i = 0; i < str.length(); ++i)
{
cout << site[i];
}
cout << endl;
}
else
{
int flag = 0; // 判断是否出现过
char tmp;
for(int i = 0; i < str.length(); ++i)
{
// 判断是否出现过
tmp = str[i];
flag = 0;
for(int j = 0; j < num; ++j)
{
if(site[j] == tmp)
{
flag = 1;
break;
}
}
if(flag == 1) continue;
site[num] = str[i];
solve(num+1);
}
}
}
int main()
{
int count = 0;
while(cin >> str)
{
sort(str.begin(), str.end()); // 按字典序输出
solve(0);
cout << endl;
}
return 0;
}
注意，字典序法要求输入的也是一个有序列。
今天在推荐一首歌，过客， 挺好听的
