找到一个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