[求助]试设计一个递归算法,产生n!个不同的全排列 - 编程论坛

#2

aipb20072007-10-11 10:09

stl:

next_permutation

#3

shohokuooo2007-10-11 10:21

?
斑竹的答案?

#4

aipb20072007-10-11 10:47

没仔细看，我以为在c++版呢，我说的是c++的库函数。

递归也是可以的：

EX:
123

保留1，23做排列{2，3}{3，2}再并上1
保留2，13做排列{1，3]{3，1}再并上2
……

这就是递归思想

#5

shohokuooo2007-10-11 21:50

斑竹的说法我怎么觉得像循环呢?
以下是我从网上找的算法,不过不是太懂.
#include <stdio.h>
void permutation(char a[], int m, int n)
{
int i;
char t;
if (m<n-1) {
permutation(a, m+1, n);
for (i=m+1;i<n;i++) {
t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n);
t=a[m]; a[m]=a[i]; a[i]=t;
}
} else
{
printf("%s ", a);
}
}
int main() {
char a[]="ABCDE";
permutation(a, 0,5);
return 0;
}

#6

shohokuooo2007-10-11 21:52

还有一个简单点的:
void genPermutation(int k, int n, int* perm) {
if (k >= n) {
for (int i = 0; i < n; ++i) {
cout << perm[i] << " ";
}
cout << endl;
}
for (int i = k; i < n; ++i) {
swap(perm[i], perm[k]);
genPermutation(k + 1, n, perm);
swap(perm[i], perm[k]);
}
}

#7

aipb20072007-10-11 22:49

以下是引用shohokuooo在2007-10-11 21:52:52的发言：
还有一个简单点的:
void genPermutation(int k, int n, int* perm) {
if (k >= n) {
for (int i = 0; i < n; ++i) {
cout << perm[i] << " ";
}
cout << endl;
}
for (int i = k; i < n; ++i) {
swap(perm[i], perm[k]);
genPermutation(k + 1, n, perm);
swap(perm[i], perm[k]);
}
}

这个就是我说的递归。
swap(perm[i], perm[k]); //保留i，交换的作用因为每个数唯一不重复
genPermutation(k + 1, n, perm); //递归，就是把保留i以后的参加递归
swap(perm[i], perm[k]); //还原

EX：
1，2，3

先保留1，交换1，1 递归23
保留2，交换2，2，递归3
保留3，交换3，3，输出；
然后一步步返回。

#8

codelet2007-11-19 11:18

自己写个“1，2，3”来模拟一下就好理解了。

genPermutation(k , n, perm)是把数组分成两部分perm[0...k]和perm[k+1...n];
然后对前一部分perm[0...k]进行排列，再接上后面的perm[k+1...n]就组成一个输出结果。

这里是一直递归到k = n 才返回，也即生成perm[0]到perm[n]的全排列。
genPermutation(k+1, n, perm） //这个是递归主体，k不停加一，直到等于n。

#9

nuciewth2007-11-19 15:31

做个广告
 https://bbs.bc-cn.net/viewthread.php?tid=90424

#10

feibiaili2007-11-22 19:24

应该没必要用递归,多麻烦啊!

#11

glglzb2012-10-22 17:34

回复 7楼 aipb2007

最后的那个不是字典序。。。。要是字典序的怎么办