C語言中遞歸和排列組合詳解
排列組合三大問題:
1.打印n個(gè)數(shù)的全排列
2.打印n個(gè)數(shù)中任意m個(gè)數(shù)的全排列
3.打印n個(gè)數(shù)中任意m個(gè)數(shù)的組合
1.打印n個(gè)數(shù)的全排列
這個(gè)題實(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)點(diǎn)。
如果用遞歸求全排列呢?
假如給了n個(gè)數(shù)123…n,求其全排列的數(shù)量,應(yīng)當(dāng)如何解決呢,下面給出一個(gè)遞歸的思路:
一開始先按照字典序排列,然后把第一個(gè)數(shù)依次和后面的數(shù)交換:
1 2 3 4 5…n
2 1 3 4 5…n
.
.
.
n 2 3 4 5…1
這是第一層遞歸,只要第一個(gè)數(shù)不同,不需要管后面n-1個(gè)數(shù)
然后在上面的每個(gè)數(shù)列中去掉第一個(gè)數(shù),對(duì)后面的n-1個(gè)數(shù)做如上操作,例如取第二組做該操作,則該第二層的遞歸為:
1 3 4 5…n
3 1 4 5…n
.
.
.
n 3 4 5…1
重復(fù)以上步驟,直到用完所有的數(shù)字。
這么講并不好理解,我從小規(guī)模到大規(guī)模來闡述這個(gè)思想:
假如只有兩個(gè)數(shù)1,2需要進(jìn)行全排列工作:
先按字典序排成1,2,這是第一層遞歸的第一組
把1去掉,只留下一個(gè)數(shù),那么只有1種情況。
第一層遞歸的第二組是2,1,這也是最后一組了
把2去掉,只留下一個(gè)數(shù),那么只有1種情況
因此兩個(gè)數(shù)的全排列是兩種情況
假如有三個(gè)數(shù)1,2,3需要進(jìn)行全排列工作:
直接看第一層遞歸的三種情況:
1、2、3;2、1、3;3、2、1
每一種情況都把第一個(gè)數(shù)去掉,就變成只有2個(gè)數(shù)的全排列了
而由上述所知,兩個(gè)數(shù)的全排列有兩種情況
那么第一層遞歸的三種情況都各自包含兩種情況即3×2=6
往后依舊借用前面的標(biāo)準(zhǔn)即可。
可是放到代碼實(shí)現(xiàn)的時(shí)候可不能做完一層刪一個(gè)數(shù),只能實(shí)現(xiàn)的了保留那層遞歸的第一個(gè)數(shù),然后繼續(xù)對(duì)下面的數(shù)做遞歸操作,這樣就完美符合了遞歸的思想。
代碼實(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);//保留第一個(gè)數(shù),進(jìn)入下一層遞歸 Swap(data[begin],data[i]);//要記得換回來 } } } int main(){ Perm(0,4); cout<<num<<endl; }
如果想要輸出這個(gè)排列,直接在Perm函數(shù)中的if語句下面做循環(huán)輸出即可。
需要注意的是:這樣輸出出來的并不一定符合字典序。
2.打印n個(gè)數(shù)中任意m個(gè)數(shù)的全排列
這個(gè)只需要把上面if語句中的條件改一下就行,改成begin==m即可
思路是一樣的,從小規(guī)模列起就好了。
3.打印n個(gè)數(shù)中任意m個(gè)數(shù)的組合
這個(gè)和上面的第2個(gè)問題就不一樣了,組合問題只需要選m個(gè)數(shù)而無須做排列,應(yīng)該怎么實(shí)現(xiàn)呢?
利用二進(jìn)制的思想,原理如下:
設(shè)一個(gè)集合{a0,a1,a2,…,an-1},子集共有2的n次方個(gè),其中包括空集。
例如一個(gè)n=3的集合{a0,a1,a2},其子集為{φ},{a0},{a1},{a1,a0},{a2},{a2,a0},{a2,a1},{a2,a1,a0}。為什么以這個(gè)順序來排呢?因?yàn)檫@樣非常符合二進(jìn)制位權(quán)值的思想。剛好可以和二進(jìn)制對(duì)應(yīng):
φ | a0 | a1 | a1 a0 | a2 | a2 a0 | a2 a1 | a2 a1 a0 |
---|---|---|---|---|---|---|---|
000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
如何輸出這些子集?,還是利用二進(jìn)制位權(quán)的思想,利用相與運(yùn)算得出其二進(jìn)制數(shù)中的每一個(gè)1,直接對(duì)應(yīng)數(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的二進(jìn)制數(shù)中的每一個(gè)1 if(i&(1<<j)) cout<<j<<" "; cout<<endl; } } int main(){ int n; cin>>n; print_subset(n); }
回到問題3,要找到任意m個(gè)數(shù)的組合,只需要做一個(gè)判斷:確定一個(gè)子集對(duì)應(yīng)的二進(jìn)制數(shù)中1的數(shù)量。這是解題的關(guān)鍵。
有一個(gè)很巧妙的做法:kk=kk&(kk-1)
重復(fù)使用該式子,直到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的二進(jìn)制數(shù)中的每一個(gè)1 if(i&(1<<j)) cout<<j<<" "; cout<<endl; } } } int main(){ int n,k; cin>>n>>k; print_subset(n,k); }
總結(jié)
到此這篇關(guān)于C語言中遞歸和排列組合詳解的文章就介紹到這了,更多相關(guān)C語言遞歸和排列組合內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++ 智能指針的模擬實(shí)現(xiàn)實(shí)例
這篇文章主要介紹了C++ 智能指針的模擬實(shí)現(xiàn)實(shí)例的相關(guān)資料,智能指針是一個(gè)類,它把普通指針封裝起來,能實(shí)現(xiàn)和普通指針同樣的功能。,需要的朋友可以參考下2017-07-07深入C/C++浮點(diǎn)數(shù)在內(nèi)存中的存儲(chǔ)方式詳解
本篇文章是對(duì)C/C++浮點(diǎn)數(shù)在內(nèi)存中的存儲(chǔ)方式進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05詳解C++調(diào)用Python腳本中的函數(shù)的實(shí)例代碼
這篇文章主要介紹了C++調(diào)用Python腳本中的函數(shù) ,需要的朋友可以參考下2018-11-11C語言實(shí)現(xiàn)個(gè)人財(cái)務(wù)管理軟件
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)個(gè)人財(cái)務(wù)管理軟件,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05VisualStudio2022不支持.NET Framework 4.0項(xiàng)目解決辦法
本文主要介紹了VisualStudio2022不支持.NET Framework 4.0項(xiàng)目解決辦法,文中通過圖文的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09