排列与组合的实现

超、凢脫俗 2022-08-04 11:48 207阅读 0赞

排列与组合，递归实现

// Permutation and Combination.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<set>
    #include<iostream>
    
    using namespace std;
    
    vector<vector<int>>aaa;
    set<set<int>>solu;
    
    void do_once(vector<int>&selected, vector<int>&remain)
    {
    	if (remain.empty())
    	{
    		aaa.push_back(selected);
    		for (int i = 0; i < selected.size(); i++)
    			cout << selected[i] << ",";
    		cout << endl;
    		return;
    	}
    	for (int i = 0; i < remain.size(); i++)
    	{
    		vector<int>se = selected,re=remain;
    		se.push_back(re[i]);
    		re.erase(re.begin()+i);
    		do_once(se, re);
    	}
    }
    
    void Permutation(int*input, int len)//全排列
    {
    	aaa.clear();
    	vector<int>remain, selected;
    	for (int i = 0; i < len; i++)
    		remain.push_back(input[i]);
    	do_once(selected, remain);
    	cout << "共有"<<aaa.size()<<"种排列" << endl;
    }
    
    
    
    
    void select(set<int>&selected, vector<int>&remain, int toselect)
    {
    	if (selected.size()==toselect)
    	{
    		if (solu.find(selected) == solu.end())
    		{
    			solu.insert(selected);
    			for (set<int>::iterator it = selected.begin(); it != selected.end(); it++)
    				cout << *it << ",";
    			cout << endl;
    		}
    		return;
    	}
    	for (int i = 0; i < remain.size(); i++)
    	{
    		vector<int> re = remain;
    		set<int>se = selected ;
    		se.insert(re[i]);
    		re.erase(re.begin() + i);
    		select(se, re,toselect);
    	}
    }
    void Combination(int*input,int len,int toselect)//组合
    {
    	solu.clear();
    	vector<int>remain;
    	set<int>selected;
    	for (int i = 0; i < len; i++)
    		remain.push_back(input[i]);
    	select(selected, remain, toselect);
    	cout << "共有" << solu.size() << "种组合" << endl;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int aa[5] = { 0, 1, 2 ,3,4};
    	Permutation(aa, 5);
    
    	//Combination(aa, 5, 2);
    
    	system("pause");
    	return 0;
    }