【C++基础】递归进阶之全排列、组合

凯奇

1.排列组合

排列：从n个元素中任取m个元素，按照一定的顺序排列起来，叫做m的全排列。
组合：从n个元素中任取m个元素为一组，m个数的组合。
注意： 排列有序，组合无序。
例：从[1,2,3]三个元素中任取两个元素进行排列组合：
排列的结果：[1,2] 、[1,3]、[2,1]、[2,3]、[3,1]、[3,2]
组合的结果：[1,2]、[1,3]、[2,3]
例题：n个元素的全排列，（n互不相同，即1，2，······n）.
#include<iostream>
#include<cmath>
using namespace std;  
//n个数全排列 ：一定要知道在第几层，该数现在的状态，回溯时的状态

int n;
int a[1000];
bool flag[1000];
void dfs(int k){
        if(k==n+1){  //递归结束条件，当到达第n+1层，代表第n层已经填完
                for(int i=1; i<=n; i++){
                        cout<<a<<" ";
                }cout<<endl;
                return;
        }
        for(int i=1; i<=n; i++){  //n个数字
                if(flag==0){  //当前数字没用过才可以排列
                        a[k]=i;   //第k层（第k个位置）填数字i
                        flag=1;  //该数已经用过，置为1
                        dfs(k+1);    //填下一层（下一个位置）
                        flag=0;   //递归回来的时候需要重新置为0
                }
        }
       
}

int main(){
        cin>>n;
        dfs(1);  //从第一层（第一个位置）开始排列
        return 0;
}
程序运行结果如下：


例2：n个数选m个数全排列
#include<iostream>
#include<cmath>
using namespace std;  
//n个数选m个数全排列 ：一定要知道在第几层，该数现在的状态，回溯时的状态

int n,m;
int a[1000];
bool flag[1000];
void dfs(int k){
        if(k==m+1){  //递归结束条件，当到达第m+1层，代表第m层已经填完
                for(int i=1; i<=m; i++){
                        cout<<a<<" ";
                }cout<<endl;
                return;
        }
        for(int i=1; i<=n; i++){  //n个数字
                if(flag==0){  //当前数字没用过才可以排列
                        a[k]=i;   //第k层（第k个位置）填数字i
                        flag=1;  //该数已经用过，置为1
                        dfs(k+1);    //填下一层（下一个位置）
                        flag=0;   //递归回来的时候需要重新置为0
                }
        }
       
}

int main(){
        cin>>n>>m;
        dfs(1);  //从第一层（第一个位置）开始排列
        return 0;
}
程序运行如下：


例3：n个不同的元素，任取m个数进行组合。（组合无序）
#include<iostream>
#include<cmath>
using namespace std;  
//n个数选m个数组合 ：当前位置数值比前一个数至少大1，
//a[k]代表当前位置上的值，它的范围是[a[k-1]+1,n]

int n,m;
int a[1000];

void dfs(int k){
        if(k==m+1){  //递归结束条件，当到达第m+1层，代表第m层已经填完
                for(int i=1; i<=m; i++){
                        cout<<a<<" ";
                }cout<<endl;
                return;
        }
        //当前位置数值比前一个数至少大1，a[k]代表当前位置上的值，它的范围是[a[k-1]+1,n]
        for(int i=a[k-1]+1; i<=n; i++){  
                a[k]=i;   //第k层（第k个位置）填数字i
                dfs(k+1);    //填下一层（下一个位置）
        }
}

int main(){
        cin>>n>>m;
        dfs(1);  //从第一层（第一个位置）开始排列
        return 0;
}
程序运行如下：


2.铺骨牌问题

有一个1*n的长方形，用1*1、1*2、1*3的骨牌铺满方格，共有几种铺法。
分析如下：


本题采用递归函数，当确定最后一块方式后，只需看前面的格子共有几种铺法即可。而最后一个格子的铺法不确定，所以要各种方案的总方案数相加才行。
即：f(n)=f(n-1)+f(n-2)+f(n-3).
程序如下：
#include<iostream>
#include<cmath>
using namespace std;  
int f(int x){
        if(x==1) return 1;  
        if(x==2) return 2;
        if(x==3) return 4;
        return f(x-1)+f(x-2)+f(x-3);  
        //共三种格子
        //f(x)的方案数为 末尾放1*1，前面总方案为f(x-1)；
        //尾放1*2，前面总方案为f(x-2)； 尾放1*3，前面总方案为f(x-3)  
}
int main(){
        int n;
        cin>>n;
        cout<<f(n);
        return 0;
}
总结

本文简单介绍了排列组合的一些基本做题思路，全排列一定要注意当前位置在第几层，当前数字是否用过，并注意回溯时数字的状态。