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}。为什么以这个顺序来排呢？因为这样非常符合二进制位权值的思想。刚好可以和二进制对应：

如何输出这些子集？，还是利用二进制位权的思想，利用相与运算得出其二进制数中的每一个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语言递归和排列组合内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！