組み合わせ(Combination)の数え上げのコードを書いてみた
あらいさんに書かんと沈めるでいわれたので書いてみた。
アルゴリズムを場当たりで考えて書いてたんですっげー時間かかった。
計5時間。
これを参考にしてからは1時間。
nCr(n個からr個取り出す組合せ)は、
http://d.hatena.ne.jp/ibaza/20080303/1204476552
1. リストの先頭要素を除いた残りのリストからr-1個を選ぶ組合せのそれぞれに先頭要素を加えたものと、
2. リストの先頭要素を除いたリストからr個を選ぶ組合せ
の合計となる(1および2はそれぞれ再帰処理となる)。
3. n = r のときは選び方は一つなのでリストをそのままリストにして返す。
4. r = 1 のときは選び方はn通りあるのでリストの要素をそれぞれリストにして返す。
5. r = 0 または r がリストの要素数より大きいときは空リストを返す。
これくらいもっと早くかけなきゃだめだなぁ。
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; }