與多個組的組合

如何以編程方式枚舉一組數字的所有可能的唯一組合？與多個組的組合

例如，如果我有集合{1,2,3,4,5,6,7,8,9,10}並且我想要3個大小爲3，3，2的子組， {[1,2,3]，[4,5,6]，[7,8]}

這將相當於{[3,2,1]，[6,5,4]，[ 7,8]}和將被認爲是一個重複的

而{[4，2,3]，[1，5,6]，[7,8]}將被認爲是一個不同的子集

顯然我正在尋找這樣做的最有效和實用的方法。我將使用相當大的N，因此算法需要可擴展。

來源

2013-07-12 cubesnyc

你知道如何迭代給定大小的所有子集嗎？ – Beta

有很多可能的分區，你可以想出。我懷疑任何東西都可以擴展到大的n。你想要做什麼？ – templatetypedef

從你的問題來看，並不完全清楚'{[4,5,6]，[1,2,3]，[7,8]}'是否與上述兩個例子一樣。我現在的答案目前不是，但你可能想明確說明。 – MvG

想到這個問題的另一種方法是作爲multiset {1, 1, 1, 2, 2, 2, 3, 3}的排列。如果這樣的置換p在位置j中的值爲i，那意味着來自原始集合的元素j應該放入分區i。

使用例如C++的模板next_permutation可以如下枚舉這些排列：

int main() { 
    int a[] = { 0, 0, 0, 1, 1, 1, 2, 2 }; 
    do { 
    // Here a[j] == i means element j of your set goes in partition i. 
    // Do whatever you want to do with the permutations generated this way. 
    } while (std::next_permutation(a, a + 8)); 
}

結果將含有10 /（3×3 2！！）= 560的不同組合！。此代碼的演示運行包括available at ideone，其中包括與問題陳述中使用的符號類似的輸出。如果你想知道如何爲gcc實現next_permutation，你可以查看the source code，但只有在目標項目的許可證允許複製該代碼時纔可以這樣做。

來源

2013-07-15 06:33:04 MvG

與多個組的組合

回答

相關問題