全排列问题(可重复排列和不可重复排列)
程序员文章站
2022-03-22 19:06:51
...
全排列
1. 不可重复全排列
全排列问题一般要求按照字典顺序排列出来.
例如:
1 2 3 1 3 2
2 1 3 2 3 1
3 1 2 3 2 1
全排列问题一般尝试用递归的方式去做,用 for 循环来解决字典序的问题.
#include <cstdio>
using namespace std;
const int N=1024;
int vis[N];
int A[N];
void print_permutation(int n,int cur)
{
if (cur==n) //cur==n 表示已经得到一组排列,输出
{
for (int i=0;i<n;i++)
printf ("%d ",A[i]);
printf ("\n");
return ;
}
for (int i=1;i<=n;i++)//for 循环中依次增大,保证了字典序
{
if (vis[i]==0)//当元素 i 没有出现,则加入当前 A 中
{
A[cur++]=i;
vis[i]=1;
print_permutation(n,cur);
cur--; //注意恢复变量,这样在下一层的排列中,元素 i 可以被选中
vis[i]=0;
}
}
}
int main()
{
int n;
scanf ("%d",&n);
print_permutation(n,0);
return 0;
}