C语言中递归和排列组合详解

C语言中递归和排列组合详解

目录

排列组合三大问题:

1.打印n个数的全排列

2.打印n个数中任意m个数的全排列

3.打印n个数中任意m个数的组合

完整代码如下:

总结

排列组合三大问题:

1.打印n个数的全排列
2.打印n个数中任意m个数的全排列
3.打印n个数中任意m个数的组合

1.打印n个数的全排列

这个题实际上是可以直接用STL中的next_permutation()函数,代码如下:

#include<bits/stdc++.h> using namespace std; int main(){ int data[4]={5,2,4,1}; sort(data,data+4);//先排序得到字典序最小的序列 do{ for(int i=0;i<4;i++) cout<<data[i]<<" "; cout<<endl; }while(next_permutation(data,data+4)); } 这样输出出来的全排列是按照字典序输出的,这是它的优点。

如果用递归求全排列呢?
假如给了n个数123…n,求其全排列的数量,应当如何解决呢,下面给出一个递归的思路:

一开始先按照字典序排列,然后把第一个数依次和后面的数交换:
1 2 3 4 5…n
2 1 3 4 5…n
.
.
.
n 2 3 4 5…1
这是第一层递归,只要第一个数不同,不需要管后面n-1个数

然后在上面的每个数列中去掉第一个数,对后面的n-1个数做如上操作,例如取第二组做该操作,则该第二层的递归为:
1 3 4 5…n
3 1 4 5…n
.
.
.
n 3 4 5…1

重复以上步骤,直到用完所有的数字。

这么讲并不好理解,我从小规模到大规模来阐述这个思想:

假如只有两个数1,2需要进行全排列工作:
先按字典序排成1,2,这是第一层递归的第一组
把1去掉,只留下一个数,那么只有1种情况。
第一层递归的第二组是2,1,这也是最后一组了
把2去掉,只留下一个数,那么只有1种情况
因此两个数的全排列是两种情况

假如有三个数1,2,3需要进行全排列工作:
直接看第一层递归的三种情况:
1、2、3;2、1、3;3、2、1
每一种情况都把第一个数去掉,就变成只有2个数的全排列了
而由上述所知,两个数的全排列有两种情况
那么第一层递归的三种情况都各自包含两种情况即3×2=6

往后依旧借用前面的标准即可。
可是放到代码实现的时候可不能做完一层删一个数,只能实现的了保留那层递归的第一个数,然后继续对下面的数做递归操作,这样就完美符合了递归的思想。
代码实现如下:

#include<bits/stdc++.h> using namespace std; #define Swap(a,b){int temp=a;a=b;b=temp;} //也可以用STL的swap函数,但是速度慢一些 int data[]={1,2,3,4,5}; int num=0; void Perm(int begin,int end){ if(begin==end)num++;//递归到底了,自然只有一种情况,num++ else{ for(int i=begin;i<=end;i++){ //i要注意从begin开始,自己和自己换的也算是一种情况 Swap(data[begin],data[i]); Perm(begin+1,end);//保留第一个数,进入下一层递归 Swap(data[begin],data[i]);//要记得换回来 } } } int main(){ Perm(0,4); cout<<num<<endl; }

如果想要输出这个排列,直接在Perm函数中的if语句下面做循环输出即可。
需要注意的是:这样输出出来的并不一定符合字典序。

2.打印n个数中任意m个数的全排列

这个只需要把上面if语句中的条件改一下就行,改成begin==m即可
思路是一样的,从小规模列起就好了。

3.打印n个数中任意m个数的组合

这个和上面的第2个问题就不一样了,组合问题只需要选m个数而无须做排列,应该怎么实现呢?
利用二进制的思想,原理如下:
设一个集合{a0,a1,a2,…,an-1},子集共有2的n次方个,其中包括空集。
例如一个n=3的集合{a0,a1,a2},其子集为{φ},{a0},{a1},{a1,a0},{a2},{a2,a0},{a2,a1},{a2,a1,a0}。为什么以这个顺序来排呢?因为这样非常符合二进制位权值的思想。刚好可以和二进制对应:

φa0a1a1 a0a2a2 a0a2 a1a2 a1 a0
000001010011100101110111

如何输出这些子集?,还是利用二进制位权的思想,利用相与运算得出其二进制数中的每一个1,直接对应数字,完全代码如下:

#include<bits/stdc++.h> using namespace std; void print_subset(int n){ for(int i=0;i<(1<<n);i++){ for(int j=0;j<n;j++)//打印子集,即打印i的二进制数中的每一个1 if(i&(1<<j)) cout<<j<<" "; cout<<endl; } } int main(){ int n; cin>>n; print_subset(n); }

回到问题3,要找到任意m个数的组合,只需要做一个判断:确定一个子集对应的二进制数中1的数量。这是解题的关键。
有一个很巧妙的做法:kk=kk&(kk-1)
重复使用该式子,直到kk为0,即可得出1的数量。

完整代码如下: #include<bits/stdc++.h> using namespace std; void print_subset(int n,int k){ for(int i=0;i<(1<<n);i++){ int num=0,kk=i; while(kk){ kk=kk&(kk-1); num++; } if(num==k){ for(int j=0;j<n;j++)//打印子集,即打印i的二进制数中的每一个1 if(i&(1<<j)) cout<<j<<" "; cout<<endl; } } } int main(){ int n,k; cin>>n>>k; print_subset(n,k); } 总结

到此这篇关于C语言中递归和排列组合详解的文章就介绍到这了,更多相关C语言递归和排列组合内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    word组合快捷键|word快速组合

    word组合快捷键|word快速组合,,word快速组合在word中如何将两张图片合在一起只需一键【组合】即可完成。以下是详细介绍:在word中如何将两

    取消组合的快捷键|取消组合的快捷键ps

    取消组合的快捷键|取消组合的快捷键ps,,取消组合的快捷键ps1,首先,在右下方的图层栏里,选中要打散的图形所在的图层。2,选好图层之后,在左侧工

    区域语言设置|区域语言设置工具

    区域语言设置|区域语言设置工具,,区域语言设置工具你好,大致的方法如下,可以参考:1、按下键盘的windows 图标,再开始菜单中单击“设置”;出现的

    c4d语言设置|c4d汉语设置

    c4d语言设置|c4d汉语设置,,1. c4d汉语设置mac版的C4D是这样的,中文字体是有的,但是是以拼音的形式存在,比如黑体就是ht。中文字体以拼音方式

    电脑宣传语|电脑宣传语言

    电脑宣传语|电脑宣传语言,,1. 电脑宣传语言1.我做好了与你过一辈子的打算,也做好了你随时要走的准备,2.每段青春都会苍老,但我希望记忆里的你