Question

C++中如何编写求出n个数的全排列

比如我输入n=3;
则输出 123 132 213 231 312 321

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

class PaiLie
{
public:
static const int ARRAY_MAX = 100;
int n;
int count;
int cache[ARRAY_MAX];
PaiLie()
{
n = 0;
count = 0;
}
void SetN()
{
printf("请输入n:\n");
char c[10];
while(true)
{
std::cin >> c;
n = atoi(c);
if(n <= ARRAY_MAX&&n > 0)
break;
else
printf("输入错误,请重新输入:\n");
}
}
void Start()
{
if(count < n)
{
for(int i = 1;i < n+1;i++)
{
if(AlreadyHasNum(i))
continue;
cache[count] = i;
count++;
Start();
count--;//保持每层递归深度的count值一致
}
}
else
{
for(int i = 0;i < n;i++)
printf("%d",cache[i]);
printf("\n");
}
}
bool AlreadyHasNum(int x)
{
for(int i = 0;i < count;i++)
{
if(cache[i] == x)
return true;
}
return false;
}
};
int main()
{

PaiLie pl;
pl.SetN();
pl.Start();
}
//cache可以改用用二叉树的，这样AlreadyHasNum(int )可以快很多，不过这样就比较难懂，而且我也懒得弄了
//Start()函数就相当于n个for循环一环套一环，深度由count < n控制

追问

能讲述下循环过程吗？就是算法是怎么算的·· 谢谢

追答

Start()函数相当于下面无限嵌套的for循环，当运行到最外面这个for循环时，count等于0,第二层为1,以此类推直到count>=n停止,而每个for循环循环的次数都为n
for()
{
语句...
for()
{
语句...
for()
{
......
}
语句...
}
语句...
}
对于12345678这个8位数，第一个for循环对映最左边的1，第二个对映2，如果不加任何限制，这8个for循环可以把11111111-88888888之间的所有数字都枚举一遍
循环顺序：比如一个3位数
111
112
113
这时最里面的for循环已经循环了3次，结束了，然后次里面的循环第一遍刚刚结束，开始循环第二次
121
122
123
...
以此类推
而我在每个for循环里写的语句，是为了当循环到前面for循环里已经出现过的数字时，自动跳过这个循环
比如已经确定了前4位数为8234,所以当从外向里数第5个循环循环到2,3,4或8时，自动跳掉，这样就在前4个循环确定的情况下使第5位数确定为1,5,6或7,然后继续确定第6个数字

我的这个算法思路其实很简单的，只有当需要列出所有的序列时有用，写完这个之后又到网上搜了一下，好像有一个什么字典序法，就是一个序列确定了之后，按字典序法的规则可以直接算出下一个序列的，这样也能枚举出所有的排列组合

Answer 2

#include <iostream.h>
#include <algorithm>
int main()
{
int i,n;
char a[20];
cout<<"n=";
cin>>n;
for(i=0;i<n;i++) a[i]='0'+i+1;
a[i]=0;
cout<<a<<endl;
while(next_permutation(a,a+n)) cout<<a<<endl;
system("pause");
return 0;
}