c++ 数组的排列子集和组合子集 排列数和组合数计算

c++ 的数组排列子集和组合子集

class Combinatorial{
    //组合
public:
    vector<int> nums;//进行抽样的数组
    vector<vector<int>> result;//保存最后的排列结果
    vector<int> res;//数组中选取组合子集,t会保存到result中

    vector<vector<int>> Combinatorial_Set(vector<int>data,int select_Num){
        if(select_Num>data.size()) cout<<"error!"<<endl;

        nums=data;
        recursion(0,select_Num);
        return result;
    }

//计算组合数long long Combinatorial_count(int a, int m){    //从m个数中选出a个    int mod = 99997867;    long long res=1;    for(int i=0;i<a;i++){        res*=(m-i);        res%=mod;    }    for(int i=1;i<=a;i++){        res/=i;    }    res%=mod;    return res;}

private: //递归函数 void recursion(int index,int select_Num){ if(res.size() == select_Num){ //长度为指定长度时，保存到ans后，返回，结束这一次递归  result.push_back(res); for(auto v:res) cout<<v;cout<<endl; return; } for(int i=index;i<nums.size();i++){ res.push_back(nums[i]); recursion(i+1,select_Num); res.pop_back(); //回溯  } } }; class Permutation{ //排列 public: vector<int> nums;//进行抽样的数组 vector<vector<int>> result;//保存最后的排列结果 vector<int> used_Flag; vector<int> res;//数组中选取排列子集  vector<vector<int>> Permutation_Set(vector<int>data,int select_Num){ if(select_Num>data.size()) cout<<"error!"<<endl; used_Flag=vector<int>(data.size(),0); nums=data; recursion(0,select_Num); cout<<result.size()<<endl; return result; } //计算排列数 int Permutation_count(int a, int m){ int res=1; for(int i=0;i<a;i++){ res*=(m-i); } return res; } private: //递归函数 void recursion(int cur_Position,int select_Num){ if(cur_Position==select_Num){ result.push_back(res); for(auto v:res) cout<<v; cout<<endl; return; } for(int i=0;i<nums.size();i++){ //如果当前元素没有被选择 if(used_Flag[i]==0){ res.push_back(nums[i]); used_Flag[i]=1; recursion(cur_Position+1,select_Num);//选择下一位 used_Flag[i]=0; res.pop_back(); } } } };

int main(){    vector<int> nums={1,2,3,4,5};    Combinatorial combinatorial;    combinatorial.Combinatorial_Set(nums,2);    Permutation permutation;    permutation.Permutation_Set(nums,2);    cout<<permutation.Permutation_count(2,5)<<endl;    return 0;}

原文链接: https://www.cnblogs.com/isYiming/p/12553414.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍