如何枚舉組合的組合從一個集合

我意識到有關於combinatorics和枚舉的問題，但我已經搜索了周圍，並沒有找到任何與我之後特別有關的任何東西。如果我錯過了某些東西，請將它指向我，然後問題就可以結束。因此，假設我們有一組N個元素，並且我們有x個正整數k1，...，kx其中Sum（k1，...，kx）< = N。我想枚舉所有方法我可以選擇（無需替換）給定尺寸的x個子集，從原始集合N.如何枚舉組合的組合從一個集合

我希望我的措辭正確。如果我沒有，一個簡單的例子。
N = 4，X = 2，K 1 = 2，K 2 = 1

我們應該列舉

{1,2} {3}
{1,2} {4}
{1,3} {2}
{1,3} {4}
{1,4} {2}
{1,4} {3}
{2， 3} {1}
{2,3} {4}
{2,4} {1}
{2,4} {3}
{3,4} {1}
{3， 4} {2}

在一般情況下，總的計數將我想爲：

C（N，K i）* C（N - K1，K2）* ... * C（ N - Sum（k1，...，kn-1），kn）。

我最初的猜測是，這可以使用堆棧相當容易地完成。在每個堆棧級別i，將使用標準組合枚舉生成子集ki，或者從每個級別的源集合中移除那些已選擇的元素，或者僅從原始集合中枚舉並跳過之前包含元素的情況。

我的問題是，有更快/更優雅的解決方案嗎？

來源

2012-10-22 kamrann

SOs格式檢查器是荒謬的，我剛剛花了45分鐘與它爭取讓它接受我的問題，因爲它告訴我我的代碼格式不正確。沒有代碼，我最初的預覽格式很好。我非常接近放棄。 – kamrann

我認爲你應該用一個遞歸函數來構建第一個子集，然後第二個... – alestanis

你的問題恰恰是枚舉multiset的排列問題。（假設您訂購了您的產品）。

首先，請注意，問題與其中Σ k＆ N，因爲如果Σ k < N，我們可以簡單地添加k _{x + 1}其值爲N - Σ k。

現在，把一些任意固定的順序的原始集合S的元素，並且產生由k的多集的每個置換 1的，K 2的，K 3的，...，K _x x's。這個multiset具有與S相同的尺寸（N），因爲這個加起來爲N.我們通過將S中的每個元素分配給其索引是多重集的置換中相應值的子集來創建S的分區。

例如，S = {apple，banana，chirimoya，date}（N = 4）。我們取k = 2和k = 1並且加上k = 1使得和爲4.（我們將忽略分配給子集3的元素）。現在，我們列舉了多集1 1 2 3的排列（其中有兩個1的，一個2，一個3，對應的K公司）：

1 1 2 3 1 2 3 1 2 1 1 3 3 1 1 2 
1 1 3 2 1 3 1 2 2 1 3 1 3 1 2 1 
1 2 1 3 1 3 1 1 2 3 1 1 3 2 1 1

我們將這些回S.。例如分區，以1 3 1 2：

apple  1 -> subset 1 
banana 3 -> unused 
chirimoya 1 -> subset 1 
date  2 -> subset 2

因此，我們必須{{apple, chirimoya}, {date}}

的standard algorithm尋找一組排列的作品一樣好上一個多集，但如果多集有很多重複的它不是最佳的。

來源

2012-10-22 16:21:40 rici

謝謝，看起來像一個非常乾淨的解決方案。 – kamrann

如何枚舉組合的組合從一個集合

回答

相關問題