全排列递归算法

算法思想

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

例如输入字符串abc,则打印出 a、b、c 所能排列出来的所有字符串 abcacbbacbcacabcba 。具体过程如下:

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

实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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这种交换后一样的情况在输出时会输出两个,于是我们需要对我们的算法进行改进,得到第二版的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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代码如下:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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函数,其函数原型为:

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

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

例如这个例子:

1
2
3
4
5
6
7
8
9
10
11
12
#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
4
5
6
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
1 2 3
2 1 3

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

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

1
2
3
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的使用