全排列 + 选择排列

DeepinScreenshot_select-area_20191003213406.png

数学公式：A(n n):需要考虑排列顺序

数学公式：A(n m): 需要考虑排列顺序,
从n个元素中选中m个元素，进行排列

递归法求解

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

// 选中排列
int res=0;
void choosePerm(int pos,int cn,int n,int k,int visit[],int nums[]){
    if(cn==k){
        for(int i=0;i<k;i++){
            cout << nums[i] << " ";
        }
        cout << endl;
        res+=1;
        return;
    }
    if(pos == n) return;
    
    for(int i=0;i<n;i++){
        if(visit[i]==0){
            visit[i]=cn+1;
            // 标记结果
            nums[cn]=i;
            choosePerm(i,cn+1,n,k, visit, nums);
            visit[i]=0;
        }
    }
}

int main(){
    // N: 0-(N-1)
    // M: 从 0-(n-1)个数中选择M个，进行全排列(跟顺序有关) 
    // 4!/(4-2)! = 12
    // 7!/(7-4)!=7*6*5*4=840
    int n=4,k=3;
    int visit[n];
    int nums[k];
    for(int i=0;i<n;i++){
        visit[i]=0;
        if(i<k){
            nums[i]=-1;
        }
    }
    choosePerm(0,0,n,k, visit, nums);
    cout << "res-count:" << res << endl;
    return 0;
}

复杂度分析

规模：N
时间复杂度：O(M^N), 选中N个元素中的一个元素后，第二个元素需要从N-1个元素中选取，依然需要遍历整个序列，第三个元素需要从N-2个元素中选取，也需要遍历整个序列。故时间复杂度: O(M^N)
空间复杂度：O(N+M), 开了大小为N 的visit数组用于标记-回溯，大小为M的nums数组用于存储每趟结果。

选择组合

DeepinScreenshot_select-area_20191003213322.png

数学公式: C(n m): 从n个元素中选出m个元素进行组合，不考虑顺序。

递归法求解

考虑每个元素有两种可能，1.选中 2.不选中
利用标记-回溯方法，记录选中过程。

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

void combina(int pos,int cn,int n,int k,int visit[]){
    if(cn==k){
        for(int i=0;i<n;i++){
            if(visit[i]==1){
                cout << i << " ";
            }
        }
        cout << endl;
        return;
    }
    if(pos==n) return;
    // 1.选择当前pos
    if(visit[pos]!=1){
        // 标记
        visit[pos]=1;
        combina(pos+1,cn+1,n,k,visit);
        // 回溯
        visit[pos]=0;
    }
    // 2.不选择当前pos
    combina(pos+1,cn,n,k,visit);
}

int main(){
    int n=7;
    int k=4;
    int visit[n];
    combina(0,0,n,k,visit);
    return 0;
}

复杂度分析

规模：N
时间复杂度：O(M^{N),每个元素有两个选择，选与不选，从N中选中第1个元素，从N-1中选中第2个元素，从N-2中选中第3个元素，时间复杂度O(M}N).
空间复杂度：O(N).只需要开大小为N的visit数组用于标记-回溯即可。

参考

csdn: https://blog.csdn.net/hf19931101/article/details/79452799