組み合わせ(Combination)の数え上げのコードを書いてみた

あらいさんに書かんと沈めるでいわれたので書いてみた。
アルゴリズムを場当たりで考えて書いてたんですっげー時間かかった。
計5時間。
これを参考にしてからは1時間。

nCr(n個からr個取り出す組合せ)は、
1. リストの先頭要素を除いた残りのリストからr-1個を選ぶ組合せのそれぞれに先頭要素を加えたものと、
2. リストの先頭要素を除いたリストからr個を選ぶ組合せ
の合計となる(1および2はそれぞれ再帰処理となる)。
3. n = r のときは選び方は一つなのでリストをそのままリストにして返す。
4. r = 1 のときは選び方はn通りあるのでリストの要素をそれぞれリストにして返す。
5. r = 0 または r がリストの要素数より大きいときは空リストを返す。

http://d.hatena.ne.jp/ibaza/20080303/1204476552

これくらいもっと早くかけなきゃだめだなぁ。
STL禁止ってのがつらかったけど。久々にSTL使わないコード書いた気がする。
コードも汚いからちゃんと使うなら整理しないと。
アロケーションしすぎだし・・・。

ってわけであらいさん、載せておきますよ。
int以外の型使いたかったらtemplateにすれば全部使えるはずー。

#include <iostream>
#include <assert.h>

int permtation(int n, int m)
{
	if( n < 0 || m < 0 || n < m )
	{
		return -1;
	}
	if( n == 0 )
	{
		return 1;
	}
	int temp = n;
	for( int i = n - 1; i >= n - m + 1; --i )
	{
		temp *= i;
	}
	return temp;
}

int combination(int n, int m)
{
	if( n < 0 || m < 0 || n < m )
	{
		return -1;
	}
	if( m == 0 )
	{
		return 1;
	}
	int perm = permtation(n, m);
	int temp = m;
	for( int i = m - 1; i > 0; --i )
	{
		temp *= i;
	}
	return perm / temp;
}

struct List
{
	int* pMember;
	int size;
	List* pNext;

	List()
		:pMember()
		,size()
		,pNext()
	{}

	~List()
	{
		if( pMember )
		{
			delete[] pMember;
		}
		if( pNext )
		{
			delete pNext;
		}
	}
}; // List

void showList(List* pList)
{
	for( int i = 0; i < pList->size; ++i )
	{
		std::cout << pList->pMember[i] << ", ";
	}
	std::cout << std::endl;
	if( pList->pNext )
	{
		showList(pList->pNext);
	}
}

List* createCombination(const List* pSrcList, int n, int m)
{
	if( m == 0 )
	{
		return NULL;
	}
	else
	if( m == 1 )
	{
		List* pList = new List;
		List* pHead = pList;
		for( int i = 0; i < n; ++i )
		{
			pList->pMember = new int[1];
			pList->pMember[0] = pSrcList->pMember[i];
			pList->size = 1;
			if( i < n - 1 )
			{
				pList->pNext = new List;
				pList = pList->pNext;
			}
		}
		return pHead;
	}
	else
	if( n == m )
	{
		List* pList = new List;
		pList->pMember = new int[pSrcList->size];
		pList->size = pSrcList->size;
		memcpy(pList->pMember, pSrcList->pMember, sizeof(int) * pSrcList->size);
		return pList;
	}
	// リストの先頭要素を除いたリストを作る
	// n == リストのサイズ
	List removeHeadMemberList;
	removeHeadMemberList.pMember = new int[n - 1];
	removeHeadMemberList.size = n - 1;
	memcpy(removeHeadMemberList.pMember, &pSrcList->pMember[1], sizeof(int) * (n - 1));
	// n-1Cr-1
	List* pRet = createCombination(&removeHeadMemberList, n - 1, m - 1);
	// 得られた結果に先頭要素を加える
	List* pCombn1r1 = new List;
	List* pRetHead = pRet;
	List* pAllCombHead = pCombn1r1;
	while( pRet != NULL )
	{
		pCombn1r1->pMember = new int[pRet->size + 1];
		pCombn1r1->size = pRet->size + 1;
		pCombn1r1->pMember[0] = pSrcList->pMember[0];
		memcpy(&pCombn1r1->pMember[1], pRet->pMember, sizeof(int) * pRet->size);
		// 次の要素へ
		pRet = pRet->pNext;
		if( pRet )
		{
			pCombn1r1->pNext = new List;
			pCombn1r1 = pCombn1r1->pNext;
		}
	}
	// 結果をコピーしたので破棄する
	delete pRetHead;

	// n-1Cr
	pRet = createCombination(&removeHeadMemberList, n - 1, m);
	pRetHead = pRet;
	List* pCombn1r = new List;
	pCombn1r1->pNext = pCombn1r;
	while( pRet != NULL )
	{
		pCombn1r->pMember = new int[pRet->size];
		pCombn1r->size = pRet->size;
		memcpy(pCombn1r->pMember, pRet->pMember, sizeof(int) * pRet->size);
		// 次の要素へ
		pRet = pRet->pNext;
		if( pRet )
		{
			pCombn1r->pNext = new List;
			pCombn1r = pCombn1r->pNext;
		}
	}
	delete pRetHead;

	return pAllCombHead;
}

int** combinationArray(int& selectionSize, int* src, int n, int m)
{
	selectionSize = combination(n, m);
	if( selectionSize == -1 )
	{
		return NULL;
	}
	int** combArray = new int*[selectionSize];
	if( selectionSize == 1 )
	{
		int* comb = new int[n];
		memcpy(comb, src, sizeof(int) * n);
		combArray[0] = comb;
	}
	else
	if( m == 1 )
	{
		for( int i = 0; i < n; ++i )
		{
			int* comb = new int[1];
			comb[0] = src[i];
			combArray[i] = comb;
		}
	}
	else
	{
		List srcList;
		srcList.pMember = new int[n];
		srcList.size = n;
		memcpy(srcList.pMember, src, sizeof(int) * n);
		List* pRet = createCombination(&srcList, n, m);

		int i = 0;
		List* pRetHead = pRet;
		while( pRet != NULL )
		{
			combArray[i] = new int[pRet->size];
			memcpy(combArray[i], pRet->pMember, sizeof(int) * pRet->size);
			++i;
			pRet = pRet->pNext;
		}
		delete pRetHead;
	}
	return combArray;
}


int main()
{
//	int ret1 = permtation(5, 4);
//	std::cout << ret1 << std::endl;
//	int ret2 = combination(10, 0);
//	std::cout << ret2 << std::endl;

	int numArray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int selectionSize;
	int m = 6;
	int** selection = combinationArray(selectionSize, numArray, sizeof(numArray)/sizeof(int), m);
	for( int i = 0; i < selectionSize; ++i )
	{
		for( int j = 0; j < m; ++j )
		{
			std::cout << selection[i][j];
			std::cout << ", ";
		}
		std::cout << std::endl;
	}

	for( int i = 0; i < selectionSize; ++i )
	{
		delete(selection[i]);
	}
	delete(selection);

	return 0;
}