排列與組合的實作

排列與組合，遞歸實作

// 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;
}