亲宝软件园·资讯

展开

C语言递归和排列组合

布布要成为最强的人 人气:0

排列组合三大问题:

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);
}

总结

加载全部内容

相关教程
猜你喜欢
用户评论