把彩球放进垃圾箱的所有可能的方法

Question

我有很多垃圾箱。每个箱子只能容纳一个球。在

比如说，我有

Na红球数

Nb蓝球数量

绿球数量

等等。在

我想找出所有可能的方法，把球放入长度（Na+Nb+Nc）的箱子里。在

例如，假设我只有两个红球和两个蓝球。我想把它们放到4个箱子里。可能的安排方式有：

R R B B
R B R B
R B B R
B R R B
B R B R
B B R R

（我希望我没有错过任何组合）

是否有任何简单的方法生成不同颜色的索引，例如：

^{pr2}$

有没有一种简单的方法在numpy中生成这个？在

垃圾箱实际上有不同的重量，比如：

[0.1, 0.3, 0.2, 0.5]

因此，对于组合rrbb表示为R at (0,1) and B at (2,3)，R的总权重是0.1+0.3=0.4，而B的总权重是0.2+0.5=0.7

我最终感兴趣的是不同排列中每种颜色的总重量，并想从另一个成本函数f（总重量（R）、总重量（B））中选择一个最佳的。如果总重量的生成可以用不同的简单方法在纽比中完成，有什么意见吗？在

Answer 1

这里有一个“多组合”实现，不需要消除重复排列。第一个参数，n，是list[Na，Nb，Nc，…]。在

它是作为递归生成器实现的，因此您可以迭代组合，而不必一次将它们都放在内存中。你在评论中说Na+Nb+。。。通常在20左右，但可能高达50或100。这意味着您几乎肯定不想将所有的组合存储在内存中。考虑一个有四个“颜色”的例子，其中Na=Nb=Nc=Nd=5。组合的数目是choose(20, 5) * choose(15, 5) * choose(10, 5) = 11732745024，其中{}是{a1}。我的电脑只有16GB的内存，所以这个数量的组合所需的存储空间将远远超过我电脑的内存。在

from itertools import combinations


def multicombinations(n, bins=None):
    if bins is None:
        bins = set(range(sum(n)))
    if len(n) == 0:
        yield []
    else:
        for c in combinations(bins, n[0]):
            for t in multicombinations(n[1:], bins - set(c)):
                yield [c] + t

它生成元组列表。也就是说，如果您对第一行的描述是“first row is:R=（0,1）B=（2,3）”，那么multicombinations([2, 2])生成的第一个值是[(0, 1), (2, 3)]。（鉴于下一步要执行的权重计算的说明，这可能不是结果的最佳格式。）

一些例子：

^{pr2}$

Answer 2

您可以使用itertools解决这个问题：

import itertools
last = None
result = []
for v in itertools.permutations(['A','A','B','B']):
    key = "".join(v)
    if key == last: continue
    last = key
    result.append(v)
print result

Answer 3

生成排列并删除重复项。在

>>> import itertools
>>> Na = 2
>>> Nb = 2
>>> p = itertools.permutations(['R']*Na + ['B']*Nb)
>>> for perm in sorted(list(set(p)), reverse=True):
...     print perm
... 
('R', 'R', 'B', 'B')
('R', 'B', 'R', 'B')
('R', 'B', 'B', 'R')
('B', 'R', 'R', 'B')
('B', 'R', 'B', 'R')
('B', 'B', 'R', 'R')