什么时候用到全排列_全排列问题 与 组合排列问题
一、全排列问题(Form.cpp)
【问题描述】
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
【输入格式】
n(1≤n≤9)
【输出格式】
由1～n组成的所有不重复的数字序列，每行一个序列。(字典序排列)
【输入样例】Form.in
3
【输出样例】Form.out
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【解析】
1.看到n只有1~9，那么最简单的方法就是：自己算出9种情况的答案，然后一个一个if来输出，对于本题一定是满分；
2.用9个for来计算答案：
#include
intmain()
{int ans[9];int num[9]={0};//用做记录此数字是否被用过
inti,i1,i2,i3,i4,i5,i6,i7,i8,i9;intn;
scanf("%d",&n);for(i1=1;i1<=n;i1++)//第一层循环
{if(num[i1-1]==1) continue;
ans[0]=i1;
num[i1-1]=1;//标记
if(n>=2)
{for(i2=1;i2<=n;i2++)//第二层循环
{if(num[i2-1]==1) continue;
ans[1]=i2;
num[i2-1]=1;//标记
if(n>=3)
{//第三层循环…………
}else{for(i=0;i<2;i++)
{
printf("%d",ans[i]);
}
printf("\n");
}
num[i2-1]=0;
}
}else{for(i=0;i<1;i++)
{
printf("%d",ans[i]);
}
printf("\n");
}
num[i1-1]=0;
}return 0;
}
这是挺麻烦的……
3.属于2的代码简化版，用函数的递归来缩短代码长度：
#include
intn;int ans[9];int num[9]={0};//用做记录此数字是否被用过
int search(intlevel);intmain()
{
scanf("%d",&n);
search(n);return 0;
}int search(intlevel)//level从n~0进行递归
{if(level==0)//到顶了
{inti;for(i=0;i
{
printf("%d",ans[i]);
}
printf("\n");return 0;
}else{inti;for(i=1;i<=n;i++)
{if(num[i-1]==1) continue;
num[i-1]=1;
ans[n-level]=i;
search(level-1);
num[i-1]=0;//两行刷黄的代码属于典型的回溯
//即“将每一层递归获得的结果保存在一个数组内，等递归结束返回时，再将结果复原” 的思想
//有利于递归时保存数据
}return 0;
}
}
PS:在search函数的else中的for里，从1-n的循环有助于将答案按照字典序输出。
2、组合的输出(Compages.cpp)
【问题描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r
现要求你用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
【输入】
一行两个自然数n、r(1
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【样例】
输入：5 3
输出： 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
【解析】
此题与第一题极为相似，当这里 n==r 时，就是第一题的解法。
然而这里的r不一定与n相等，大家对比一下第一题的程序，发现有什么变化了吗？
火眼金睛大比拼：
#include
intn,r;int ans[9];int num[9]={0};//用做记录此数字是否被用过
int search(intlevel);intmain()
{
scanf("%d%d",&n,&r);
search(r);return 0;
}int search(intlevel)
{if(level==0)//到顶了
{inti;for(i=0;i
{
printf("%d",ans[i]);
}
printf("\n");return 0;
}else{inti;for(i=1;i<=n;i++)
{if(num[i-1]==1) continue;
num[i-1]=1;
ans[r-level]=i;
search(level-1);
num[i-1]=0;
}return 0;
}
}
没错，我们将控制 寻找数字个数 的变量全部换成了r，这样它就和第一题解法一模一样了。(回溯)