6

假设我有一个包含 6 个球（3 个白色和 3 个黑色）的袋子。我想找到给定长度的所有可能子集，而不考虑顺序。在上面的例子中，我只能从袋子里抽出 3 个球的 4 种组合：

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

我已经在我选择的语言中找到了一个完全可以做到这一点的库，但是我发现它对于更多的数字来说很慢。例如，一个袋子包含 15 个白色、1 个黑色、1 个蓝色、1 个红色、1 个黄色和 1 个绿色，10 个球只有 32 种组合，但需要 30 秒才能产生结果。

有没有一种有效的算法可以找到我可以自己实现的所有组合？也许这个问题并不像我最初想的那么微不足道......

注意：我什至不确定表达这一点的正确技术词，所以请随时更正我的帖子标题。

4

2 回答 2

5

您可以比一般的选择算法做得更好。关键的见解是同时处理每种颜色的球，而不是一个接一个地处理这些球。

我在 python 中创建了该算法的未优化实现，可以在毫秒内正确找到测试用例的 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
于 2013-10-03T17:40:04.480 回答
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
>
于 2013-10-03T18:31:56.293 回答