如题:设计一个递归算法,产生n!个不同的全排列
(注意:是n!个不同的全排列,不是求n!的数值)
不要求写出原代码用类C写写算法就可以,我只想知道算法,谢谢大家!
有能力的帮帮在下,不胜感谢!

stl:

next_permutation

?
斑竹的答案?

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

递归也是可以的：

EX:
123

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

这就是递归思想

斑竹的说法我怎么觉得像循环呢?
以下是我从网上找的算法,不过不是太懂.
#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;
}

还有一个简单点的:
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，输出；
然后一步步返回。

自己写个“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。

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

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