n選m排列問題的遞歸算法

n選m排列是一個經(jīng)典算法題，如果m = n則稱為全排列。

n選m排列問題的遞歸算法邏輯為：

1，將m個數(shù)的排列分為兩部分：一部分為包含某個數(shù)k(1 <= k <= n)的m排列，一部分為不包含k的m排列；

2，對于包含k的排列，又可以分為兩部分：一部分為包含某個數(shù)s(k < s <= n)的m-1排列，一部分為不包含s的m-1排列；

3，對于2步所得m-1排列，將k插入到每一個排列中的m個位置可以得到m個新的m排列；

4，同步驟2，對于不包含k的排列可以進行類似的操作，最終將得到所有的n個元素的m排列。

遞歸算法的偽代碼：

Begin:
input m, n;
if m is bigger than n, then set m = n;
if m is smaller than or equal to 0, then return;
if n is smaller than or equal to 0, then return;

PartA: get m permutation contains 1;
PartB: get m permutation not contains 1;

collect two permutations;

End;

PartA:
input k, m, n;
if m is equal to 1, then return 1 permutation only k;

PartA: get m-1 permutation contains k+1;

if m is smaller than (n - k + 1), then:
PartB: get m-1 permutation not contains k+1;

collect two permutation sets in one set;

foreach m-1 permutation, insert k to m different positions in this permutation, then get m permutation sets;

 End;

PartB:
input k, m, n
if m is equal to 1, then return (n-k+1) ones 1 permutation, each 1 permutation only contains k ~ n one element;

PartA: get m permutation contains k;
if m is smaller than (n - k + 1), then:
PartB: get m permutation not contains k;

collect two m permutation;

End;

C++代碼實現(xiàn)：

#include 
#include 
#include 

using namespace std;


void FullPremutationPartA(int firstNo, int numPremu, int numCount, vector> &vec);

void FullPremutationPartB(int secNo, int numPremu, int numCount, vector> &vec);

void FullPremutation(int numPremu, int numCount, vector> &vec);

int main()
{
	int numPremu,
		numCount;
	vector> vec;

	cout << "Input number of Premutation: ";
	cin >> numPremu;
	cout << "Input number of count: ";
	cin >> numCount;


	FullPremutation(numPremu, numCount, vec);

	int vecSize = vec.size();
	//for (int vecIndex = 0; vecIndex < vecSize; vecIndex++)
	//{
	//	int termSize = vec[vecIndex].size();
	//	for (int tIndex = 0; tIndex < termSize; tIndex++)
	//	{
	//		cout << vec[vecIndex][tIndex] << "t";
	//	}

	//	cout << endl;
	//}
	cout << "count = " << vecSize << endl;

	return 0;
}




void FullPremutation(int numPremu, int numCount, vector> &vec)
{
	if ((numPremu <= 0) || (numCount <= 0))
		return;

	if (1 == numPremu)
	{
		for (int premuIndex = 1; premuIndex <= numCount; premuIndex++)
		{
			vector premuvec;
			premuvec.push_back(premuIndex);
			vec.push_back(premuvec);
		}

		return;
	}

	if (1 == numCount)
	{
		vector premuvec;
		premuvec.push_back(numCount);
		vec.push_back(premuvec);
		return;
	}

	if (numPremu > numCount)
	{
		FullPremutation(numCount, numCount, vec);
		return;
	}

	vector> PartAVector;
	FullPremutationPartA(1, numPremu, numCount, PartAVector);
	vec.insert(vec.end(), PartAVector.begin(), PartAVector.end());

	if (numPremu < numCount)
	{
		vector> PartBVector;
		FullPremutationPartB(2, numPremu, numCount, PartBVector);
		vec.insert(vec.end(), PartBVector.begin(), PartBVector.end());
	}

	return;
}


/****************************************************************
 * Function that process Premutation from firstNo to numCount
 * with count number of numPremu containing firstNo.
*****************************************************************/
void FullPremutationPartA(int firstNo, int numPremu, int numCount, vector> &vec)
{
	if (firstNo > numCount)
		return;


	if ((1 == numPremu) || (firstNo == numCount))
	{
		vector premuVec;
		premuVec.push_back(firstNo);
		vec.push_back(premuVec);
		return;
	}


	vector> PartAVector;
	FullPremutationPartA(firstNo + 1, numPremu - 1, numCount, PartAVector);

	vector> nunFullVector;
	nunFullVector.insert(nunFullVector.end(), PartAVector.begin(), PartAVector.end());
	
	if (numPremu < (numCount - firstNo + 1))
	{
		vector> PartBVector;
		FullPremutationPartB(firstNo + 2, numPremu - 1, numCount, PartBVector);
	
		nunFullVector.insert(nunFullVector.end(), PartBVector.begin(), PartBVector.end());
	}
		
	
	int fullSize = nunFullVector.size();
	int termSize = nunFullVector[0].size();
	vec.resize(fullSize * (termSize + 1));
	int vecIndex = 0;
	
	for (int preIndex = 0; preIndex < fullSize; preIndex++)
	{
		vector tmpVector;
		tmpVector.resize(termSize + 1);
		copy(nunFullVector[preIndex].begin(), nunFullVector[preIndex].end(), tmpVector.begin());
		tmpVector[termSize] = firstNo;
		vec[vecIndex].assign(tmpVector.begin(), tmpVector.end());
		vecIndex++;
		
		for (int termIndex = termSize; termIndex > 0 ; termIndex--)
		{
			tmpVector[termIndex] = tmpVector[termIndex - 1];
			tmpVector[termIndex - 1] = firstNo;

			vec[vecIndex].assign(tmpVector.begin(), tmpVector.end());
			vecIndex++;
		}
	}

	return;
}

/****************************************************************
 * Function that process Premutation from SecNo to numCount
 * with count number of numPremu
*****************************************************************/
void FullPremutationPartB(int secNo, int numPremu, int numCount, vector> &vec)
{
	if (secNo > numCount)
		return;

	if (1 == numPremu)
	{
		for (int premuIndex = secNo; premuIndex <= numCount; premuIndex++)
		{
			vector premuVec;
			premuVec.push_back(premuIndex);
			vec.push_back(premuVec);			
		}

		return;
	}

	if (secNo == numCount)
	{
		vector premuVec;
		premuVec.push_back(secNo);
		vec.push_back(premuVec);
		return;
	}	

	
	vector> PartAVector;
	FullPremutationPartA(secNo, numPremu, numCount, PartAVector);
	vec.insert(vec.end(), PartAVector.begin(), PartAVector.end());

	if (numPremu < (numCount - secNo + 1))
	{
		vector> PartBVector;
		FullPremutationPartB(secNo + 1, numPremu, numCount, PartBVector);
		vec.insert(vec.end(), PartBVector.begin(), PartBVector.end());
	}

	return;
}

在實現(xiàn)的過程中，發(fā)現(xiàn)設計很重要，剛開始沒有進行詳細的設計，僅僅根據(jù)一點思路去實現(xiàn)，走了很多彎路，也花了很多的時間。所以算法設計一定要設計清晰，在實現(xiàn)中才能有的放矢的完善細節(jié)。