C語言中遞歸和排列組合詳解

更新時間：2022年01月13日 10:08:04 作者：布布要成為最強的人

大家好，本篇文章主要講的是C語言中遞歸和排列組合詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

排列組合三大問題：

1.打印n個數(shù)的全排列
2.打印n個數(shù)中任意m個數(shù)的全排列
3.打印n個數(shù)中任意m個數(shù)的組合

1.打印n個數(shù)的全排列

這個題實際上是可以直接用STL中的next_permutation()函數(shù)，代碼如下：

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

這樣輸出出來的全排列是按照字典序輸出的，這是它的優(yōu)點。

如果用遞歸求全排列呢？
假如給了n個數(shù)123…n，求其全排列的數(shù)量，應當如何解決呢，下面給出一個遞歸的思路：

一開始先按照字典序排列，然后把第一個數(shù)依次和后面的數(shù)交換：
1 2 3 4 5…n
2 1 3 4 5…n
.
.
.
n 2 3 4 5…1
這是第一層遞歸，只要第一個數(shù)不同，不需要管后面n-1個數(shù)

然后在上面的每個數(shù)列中去掉第一個數(shù)，對后面的n-1個數(shù)做如上操作，例如取第二組做該操作，則該第二層的遞歸為：
1 3 4 5…n
3 1 4 5…n
.
.
.
n 3 4 5…1

重復以上步驟，直到用完所有的數(shù)字。

這么講并不好理解，我從小規(guī)模到大規(guī)模來闡述這個思想：

假如只有兩個數(shù)1,2需要進行全排列工作：
先按字典序排成1,2，這是第一層遞歸的第一組
把1去掉，只留下一個數(shù)，那么只有1種情況。
第一層遞歸的第二組是2,1，這也是最后一組了
把2去掉，只留下一個數(shù)，那么只有1種情況
因此兩個數(shù)的全排列是兩種情況

假如有三個數(shù)1,2，3需要進行全排列工作：
直接看第一層遞歸的三種情況：
1、2、3；2、1、3；3、2、1
每一種情況都把第一個數(shù)去掉，就變成只有2個數(shù)的全排列了
而由上述所知，兩個數(shù)的全排列有兩種情況
那么第一層遞歸的三種情況都各自包含兩種情況即3×2=6

往后依舊借用前面的標準即可。
可是放到代碼實現(xiàn)的時候可不能做完一層刪一個數(shù)，只能實現(xiàn)的了保留那層遞歸的第一個數(shù)，然后繼續(xù)對下面的數(shù)做遞歸操作，這樣就完美符合了遞歸的思想。
代碼實現(xiàn)如下：

#include<bits/stdc++.h>
using namespace std;
#define Swap(a,b){int temp=a;a=b;b=temp;}
//也可以用STL的swap函數(shù)，但是速度慢一些
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);//保留第一個數(shù)，進入下一層遞歸
            Swap(data[begin],data[i]);//要記得換回來
        }
    }
}
int main(){
	Perm(0,4);
	cout<<num<<endl;
}

如果想要輸出這個排列，直接在Perm函數(shù)中的if語句下面做循環(huán)輸出即可。
需要注意的是：這樣輸出出來的并不一定符合字典序。

2.打印n個數(shù)中任意m個數(shù)的全排列

這個只需要把上面if語句中的條件改一下就行，改成begin==m即可
思路是一樣的，從小規(guī)模列起就好了。

3.打印n個數(shù)中任意m個數(shù)的組合

這個和上面的第2個問題就不一樣了，組合問題只需要選m個數(shù)而無須做排列，應該怎么實現(xiàn)呢？
利用二進制的思想，原理如下：
設一個集合{a0,a1,a2,…,an-1}，子集共有2的n次方個，其中包括空集。
例如一個n=3的集合{a0,a1,a2}，其子集為{φ},{a0},{a1},{a1,a0},{a2},{a2,a0},{a2,a1},{a2,a1,a0}。為什么以這個順序來排呢？因為這樣非常符合二進制位權值的思想。剛好可以和二進制對應：

φ	a0	a1	a1 a0	a2	a2 a0	a2 a1	a2 a1 a0
000	001	010	011	100	101	110	111

如何輸出這些子集？，還是利用二進制位權的思想，利用相與運算得出其二進制數(shù)中的每一個1，直接對應數(shù)字，完全代碼如下：

#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的二進制數(shù)中的每一個1
            if(i&(1<<j))
                cout<<j<<" ";
        cout<<endl;
    }
}
int main(){
	int n;
	cin>>n;
	print_subset(n);
}

回到問題3，要找到任意m個數(shù)的組合，只需要做一個判斷：確定一個子集對應的二進制數(shù)中1的數(shù)量。這是解題的關鍵。
有一個很巧妙的做法：kk=kk&(kk-1)
重復使用該式子，直到kk為0，即可得出1的數(shù)量。

完整代碼如下：

#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的二進制數(shù)中的每一個1
                if(i&(1<<j))
                    cout<<j<<" ";
            cout<<endl;
        }
    }
}
int main(){
	int n,k;
	cin>>n>>k;
	print_subset(n,k);
}