全排列 + 選擇排列

DeepinScreenshot_select-area_20191003213406.png

數(shù)學(xué)公式：A(n n):需要考慮排列順序

數(shù)學(xué)公式：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;
            // 標記結(jié)果
            nums[cn]=i;
            choosePerm(i,cn+1,n,k, visit, nums);
            visit[i]=0;
        }
    }
}

int main(){
    // N: 0-(N-1)
    // M: 從 0-(n-1)個數(shù)中選擇M個，進行全排列(跟順序有關(guān)) 
    // 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;
}

復(fù)雜度分析

規(guī)模：N
時間復(fù)雜度：O(M^N), 選中N個元素中的一個元素后，第二個元素需要從N-1個元素中選取，依然需要遍歷整個序列，第三個元素需要從N-2個元素中選取，也需要遍歷整個序列。故時間復(fù)雜度: O(M^N)
空間復(fù)雜度：O(N+M), 開了大小為N 的visit數(shù)組用于標記-回溯，大小為M的nums數(shù)組用于存儲每趟結(jié)果。

選擇組合

DeepinScreenshot_select-area_20191003213322.png

數(shù)學(xué)公式: 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;
}

復(fù)雜度分析

規(guī)模：N
時間復(fù)雜度：O(M^{N),每個元素有兩個選擇，選與不選，從N中選中第1個元素，從N-1中選中第2個元素，從N-2中選中第3個元素，時間復(fù)雜度O(M}N).
空間復(fù)雜度：O(N).只需要開大小為N的visit數(shù)組用于標記-回溯即可。

參考

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