排列组合的实现

简单算法：

从前往后（或者从后往前）每次交换一个位置。当存在一个到达最后位置时，需要调整整个数组的位置。将所有的0（1）的位置向后整体移动一位。

直到结束。

 

 

#include <iostream>
#include <assert.h>
#include <new>
using namespace std;

void PrintArr(const int* pnArr, const int nLen);
int Combin(const int m, const int n);
bool IsEndofCombin(const int* pnArr, const int m, const int n);
bool ChangeArr(int* pnArr, const int m, const int n);

int main()
{
	int m = 0;
	int n = 0;

	while (true)
	{
		cout << "please input m:";
		cin >> m;

		cout << "please input n:";
		cin >> n;

		Combin(m, n);
	}

	return 0;
}

void PrintArr(const int* pnArr, const int nLen)
{
	assert(pnArr && nLen > 0);

	int i = 0;
	for (i = 0; i < nLen; i++)
	{
		if (pnArr[i] > 0)
		{
			cout << char('A' + i);
		}
	}

	cout << endl;
}

bool IsEndofCombin(const int* pnArr, const int m, const int n)
{
	assert(pnArr && m > 0 && n > 0 && m >= n);
	bool bResvr = n > m / 2 ? true : false;

	if (m == n)
	{
		return false;
	}

	int i = 0;
	if (bResvr)
	{
		for (i = 0; i < m - n; i++)
		{
			if (pnArr[i] > 0)
			{
				return false;
			}
		}
	}
	else
	{
		for (i = n; i < m; i++)
		{
			if (pnArr[i] < 0)
			{
				return false;
			}
		}
	}

	return true;
}

bool AdjustArr(int* pnArr, const int m, const int n)
{
	assert(pnArr && m > 0 && n > 0 && m >= n);

	if (m == n)
	{
		return false;
	}

	bool bResvr = n > m / 2 ? true : false;
	int i = 0;
	int j = 0;

	if (bResvr)
	{
		for (i = 0; i < m - n; i++)
		{
			if (pnArr[i] > 0)
			{
				break;
			}
		}

		//如果交换完成
		if (i >= m -n )
		{
			return false;
		}

		//开始交换
		if (pnArr[0] > 0)
		{
			return false;
		}

		//找到需要移动的位置,从此位置向前移动一位
		for (i = m - 1; i >= 0; i--)
		{
			if (pnArr[i] <= 0)
			{
				break;
			}
		}

		for (j = 0; j < m; j++)
		{
			pnArr[j] = 1;
		}

		for (j = 0; j < m - n; j++)
		{
			pnArr[--i] = 0;
		}

		return true;
	}
	else
	{
		for (i = 0; i < m - n; i++)
		{
			if (pnArr[m - i - 1] <= 0)
			{
				break;
			}
		}

		//交换完毕
		if (i >= m - n)
		{
			return false;
		}

		//开始交换
		if (pnArr[m - 1] <= 0)
		{
			return false;
		}

		//找到需要移动的位置,从此位置向后移动一位
		for (i = 0; i < m; i++)
		{
			if (pnArr[i] > 0)
			{
				break;
			}
		}

		for (j = 0; j < m; j++)
		{
			pnArr[j] = 0;
		}

		for (j = 0; j < n; j++)
		{
			pnArr[++i] = 1;
		}

		return true;
	}

	return true;
}

bool ChangeArr(int* pnArr, const int m, const int n)
{
	assert(pnArr && m > 0 && n > 0 && m >= n);

	if (m == n)
	{
		return false;
	}

	bool bResvr = n > m / 2 ? true : false;
	int i = 0;
	int nPlace = 0;
	int nTime = 0;

	if (bResvr)
	{
		nPlace = 0;
		for (nTime = 0; nTime < m - n; nTime++)
		{
			for (i = nPlace; i < m; i++)
			{
				if (pnArr[i] <= 0)
				{
					//change
					if (i > nPlace)
					{
						int nTmp = pnArr[i];
						pnArr[i] = pnArr[i - 1];
						pnArr[i - 1] = nTmp;

						return true;
					}
					else
					{
						nPlace++;
						break;
					}
				}

			}
		}
	}
	else
	{
		nPlace = m - 1;
		for (nTime = 0; nTime < m - n; nTime++)
		{
			for (i = nPlace; i >= 0; i--)
			{
				if (pnArr[i] > 0)
				{
					//change
					if (i < nPlace)
					{
						int nTmp = pnArr[i];
						pnArr[i] = pnArr[i + 1];
						pnArr[i + 1] = nTmp;

						return true;
					}
					else
					{
						nPlace--;
						break;
					}
				}
			}
		}
	}

	return false;
}

//get n combin from m numbers
int Combin(const int m, const int n)
{
	assert(m > 0 && n > 0 && m >= n);

	int* pnArr = new(nothrow) int[m];
	if (NULL == pnArr)
	{
		return -1;
	}

    //int aray
	memset(pnArr, 0, sizeof(int) * m);

	int i = 0;

	for (i = 0; i < m; i++)
	{
		pnArr[i] = i < n ? 1 : 0;
	}

	int nCount = 0;

	PrintArr(pnArr, m);
	nCount++;

	while (true)
	{
		if (!ChangeArr(pnArr, m, n))
		{
			cout << "total count:" << nCount << endl;
			break;
		}

		PrintArr(pnArr, m);
		nCount++;

		//adjust value
		if (AdjustArr(pnArr, m, n))
		{
			PrintArr(pnArr, m);
			nCount++;
		}
	}

	return 0;
}