找到一個multiset的所有子集

Question

假設我有一個包含6個球（3個白色和3個黑色）的袋子。 我想查找給定長度的所有可能的子集，而不考慮順序。在上面的情況下，有我可以從袋繪製3個球的只有4個組合：

• 2白色和1個黑
• 2黑色和1個白色
• 3白色
• 3黑

我已經在我的語言選擇中找到了一個圖書館，但是我發現它對於更多數字來說很慢。例如，對於包含15個白色，1個黑色，1個藍色，1個紅色，1個黃色和1個綠色的袋子，僅有32個10個球的組合，但需要30秒才能得出結果。

是否有一個有效的算法可以找到我可以實現自己的所有組合？也許這個問題並不像我第一次想到的那麼微不足道......

注意：我甚至不確定正確的技術詞彙來表達這一點，所以隨時糾正我的文章的標題。

Answer 1

不，你不需要搜索所有可能的選擇。一個簡單的遞歸算法（就像@recursive給出的算法）會給你答案。如果你正在尋找一個實際輸出所有組合的函數，而不僅僅是多少個，這裏是一個用R編寫的版本。我不知道你在用什麼語言工作，但是翻譯這個應該是非常簡單的任何東西，儘管代碼可能會更長，因爲R擅長這種事情。

allCombos<-function(len, ## number of items to sample 
        x, ## array of quantities of balls, by color 
        names=1:length(x) ## names of the colors (defaults to "1","2",...) 
){ 
    if(length(x)==0) 
    return(c()) 

    r<-c() 
    for(i in max(0,len-sum(x[-1])):min(x[1],len)) 
     r<-rbind(r,cbind(i,allCombos(len-i,x[-1]))) 

    colnames(r)<-names 
    r 
} 

下面是輸出：

> allCombos(3,c(3,3),c("white","black")) 
    white black 
[1,]  0  3 
[2,]  1  2 
[3,]  2  1 
[4,]  3  0 
> allCombos(10,c(15,1,1,1,1,1),c("white","black","blue","red","yellow","green")) 
     white black blue red yellow green 
[1,]  5  1 1 1  1  1 
[2,]  6  0 1 1  1  1 
[3,]  6  1 0 1  1  1 
[4,]  6  1 1 0  1  1 
[5,]  6  1 1 1  0  1 
[6,]  6  1 1 1  1  0 
[7,]  7  0 0 1  1  1 
[8,]  7  0 1 0  1  1 
[9,]  7  0 1 1  0  1 
[10,]  7  0 1 1  1  0 
[11,]  7  1 0 0  1  1 
[12,]  7  1 0 1  0  1 
[13,]  7  1 0 1  1  0 
[14,]  7  1 1 0  0  1 
[15,]  7  1 1 0  1  0 
[16,]  7  1 1 1  0  0 
[17,]  8  0 0 0  1  1 
[18,]  8  0 0 1  0  1 
[19,]  8  0 0 1  1  0 
[20,]  8  0 1 0  0  1 
[21,]  8  0 1 0  1  0 
[22,]  8  0 1 1  0  0 
[23,]  8  1 0 0  0  1 
[24,]  8  1 0 0  1  0 
[25,]  8  1 0 1  0  0 
[26,]  8  1 1 0  0  0 
[27,]  9  0 0 0  0  1 
[28,]  9  0 0 0  1  0 
[29,]  9  0 0 1  0  0 
[30,]  9  0 1 0  0  0 
[31,]  9  1 0 0  0  0 
[32,] 10  0 0 0  0  0 
> 

Answer 2

你可以比一般選擇算法做得更好。關鍵的見解是同時對待每種顏色的球，而不是逐一對待每一個球。

我創建了一個未經優化的實現這個算法蟒在毫秒準確找到你的測試用例的32結果：

def multiset_choose(items_multiset, choose_items): 
    if choose_items == 0: 
     return 1 # always one way to choose zero items 
    elif choose_items < 0: 
     return 0 # always no ways to choose less than zero items 
    elif not items_multiset: 
     return 0 # always no ways to choose some items from a set of no items 
    elif choose_items > sum(item[1] for item in items_multiset): 
     return 0 # always no ways to choose more items than are in the multiset 

    current_item_name, current_item_number = items_multiset[0] 
    max_current_items = min([choose_items, current_item_number]) 

    return sum(
     multiset_choose(items_multiset[1:], choose_items - c) 
     for c in range(0, max_current_items + 1) 
    ) 

而且測試：

print multiset_choose([("white", 3), ("black", 3)], 3) 
# output: 4 

print multiset_choose([("white", 15), ("black", 1), ("blue", 1), ("red", 1), ("yellow", 1), ("green", 1)], 10) 
# output: 32