首页 > 代码库 > 生成排列的递归方法
生成排列的递归方法
一 提议描述：
输入正整数n，按照字典序从小到大的顺序输出前n个数的所有排列。
二 思路分析：
对此问题用递归的思想解决：先输出所有以1开头的排列（递归调用），然后输出以2开头的排列（递归调用），接着以3开头的排列，„，最后才是以n开头的排列。
以1开头的排列的特点是：第一位是1，后面是按字典序的2～9的排列。所以在设计递归函数需要以下参数：
（1）已经确定的“前缀”序列，以便输出；
（2）需要进行全排列的元素集合，以便依次选做第一个元素。 这样，写出以下的伪代码：
void print_permutation(序列A，集合S)
{
if(S为空) 输出序列A;
else 按照从小到大顺序依次考虑S的每个元素v
{
print_permutation(在A的末尾填加v后得到的新序列，S-{v});
}
}
上面的递归函数中递归边界是S为空的情形，可以直接输出序列A；若S不为空，则按从小到大的顺序考虑S中的每个元素，每次递归调用以A开头。
下面考虑程序的实现。用数组表示序列A，集合S可以由序列A完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法得到数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置cur。声明一个足够大的数组A，然后调用print_permutation(n,A,0)，即可按字典序输出1～n的所有排列。
AC代码：
1 #include<iostream> 2 using namespace std; 3 int s[100]; 4 void order(int n,int *a,int cur) 5 { 6 if(cur==n) 7 {for(int i=0;i<n;i++) 8 cout<<a[i]; 9 cout<<endl;}10 else11 {12 for(int i=1;i<=n;i++)13 {14 int ok=1;15 for(int j=0;j<cur;j++)//寻找在已经排好的序列里面是否有等于i的数字16 if(a[j]==i) ok=0;17 if(ok)//没有则把数字引入到数组中18 {19 a[cur]=i;20 order(n,a,cur+1);//如果找到则进入下一层递归21 } 22 }23 }24 }25 int main()26 {27 int n;28 cin>>n;29 order(n,s,0);30 return 0;31 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。