所有可能的方法將綵球放入垃圾箱

Question

我有一些垃圾箱。每個容器只容納一個球。

比方說，我有一個紅球

娜號 藍色球

的

鈮數 綠球

等等

數控數。

我想找出將球放入長度爲（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 

（我希望我沒有錯過任何組合）

有沒有簡單的方法來產生不同顏色的指標，例如：

First row is : R=(0,1) B=(2,3) 
Second row is : R=(0,2) B=(1,3) 

有沒有一種簡單的方法在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（total_weight（R），total_weight（B））中選擇最好的一個。如果總體重量的產生可以在numpy中以不同的簡單方式完成，那麼是否有任何意見？

Answer 1

這裏的「多組合」的實現，不需要消除重複排列。第一個參數n是列表[Na，Nb，Nc，...]。

它是作爲一個遞歸生成器實現的，所以你可以遍歷這些組合，而不一次將它們全部存儲在內存中。你在評論中說，Na + Nb + ...通常在20左右，但可能高達50或100。這意味着你幾乎肯定不想將所有組合存儲在內存中。考慮具有四種「顏色」的示例，其中Na = Nb = Nc = Nd = 5。組合的數目是choose(20, 5) * choose(15, 5) * choose(10, 5) = 11732745024，其中choose(n, k)是binomial coefficient。我的電腦只有16 GB的RAM，因此這些組合所需的存儲空間遠遠超過我的電腦內存。

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 

它生成元組列表。也就是說，如果您對第一行的描述是「第一行是：R =（0,1）B =（2,3）」，則multicombinations([2, 2])生成的第一個值爲[(0, 1), (2, 3)]。 （這可能不是對結果的最佳格式，因爲你下一步想做的權重計算的描述。）

一些例子：

In [74]: list(multicombinations([2, 2])) 
Out[74]: 
[[(0, 1), (2, 3)], 
[(0, 2), (1, 3)], 
[(0, 3), (1, 2)], 
[(1, 2), (0, 3)], 
[(1, 3), (0, 2)], 
[(2, 3), (0, 1)]] 

In [75]: list(multicombinations([3, 2])) 
Out[75]: 
[[(0, 1, 2), (3, 4)], 
[(0, 1, 3), (2, 4)], 
[(0, 1, 4), (2, 3)], 
[(0, 2, 3), (1, 4)], 
[(0, 2, 4), (1, 3)], 
[(0, 3, 4), (1, 2)], 
[(1, 2, 3), (0, 4)], 
[(1, 2, 4), (0, 3)], 
[(1, 3, 4), (0, 2)], 
[(2, 3, 4), (0, 1)]] 

In [76]: list(multicombinations([2, 3, 2])) 
Out[76]: 
[[(0, 1), (2, 3, 4), (5, 6)], 
[(0, 1), (2, 3, 5), (4, 6)], 
[(0, 1), (2, 3, 6), (4, 5)], 
[(0, 1), (2, 4, 5), (3, 6)], 
[(0, 1), (2, 4, 6), (3, 5)], 
[(0, 1), (2, 5, 6), (3, 4)], 
[(0, 1), (3, 4, 5), (2, 6)], 
[(0, 1), (3, 4, 6), (2, 5)], 
[(0, 1), (3, 5, 6), (2, 4)], 
[(0, 1), (4, 5, 6), (2, 3)], 
[(0, 2), (1, 3, 4), (5, 6)], 
[(0, 2), (1, 3, 5), (4, 6)], 
[(0, 2), (1, 3, 6), (4, 5)], 
[(0, 2), (1, 4, 5), (3, 6)], 
[(0, 2), (1, 4, 6), (3, 5)], 
[(0, 2), (1, 5, 6), (3, 4)], 
[(0, 2), (3, 4, 5), (1, 6)], 
[(0, 2), (3, 4, 6), (1, 5)], 
[(0, 2), (3, 5, 6), (1, 4)], 
[(0, 2), (4, 5, 6), (1, 3)], 
[(0, 3), (1, 2, 4), (5, 6)], 
[(0, 3), (1, 2, 5), (4, 6)], 
[(0, 3), (1, 2, 6), (4, 5)], 
[(0, 3), (1, 4, 5), (2, 6)], 
[(0, 3), (1, 4, 6), (2, 5)], 
[(0, 3), (1, 5, 6), (2, 4)], 
[(0, 3), (2, 4, 5), (1, 6)], 
[(0, 3), (2, 4, 6), (1, 5)], 
[(0, 3), (2, 5, 6), (1, 4)], 
[(0, 3), (4, 5, 6), (1, 2)], 
[(0, 4), (1, 2, 3), (5, 6)], 
[(0, 4), (1, 2, 5), (3, 6)], 
[(0, 4), (1, 2, 6), (3, 5)], 
[(0, 4), (1, 3, 5), (2, 6)], 
[(0, 4), (1, 3, 6), (2, 5)], 
[(0, 4), (1, 5, 6), (2, 3)], 
[(0, 4), (2, 3, 5), (1, 6)], 
[(0, 4), (2, 3, 6), (1, 5)], 
[(0, 4), (2, 5, 6), (1, 3)], 
[(0, 4), (3, 5, 6), (1, 2)], 
[(0, 5), (1, 2, 3), (4, 6)], 
[(0, 5), (1, 2, 4), (3, 6)], 
[(0, 5), (1, 2, 6), (3, 4)], 
[(0, 5), (1, 3, 4), (2, 6)], 
[(0, 5), (1, 3, 6), (2, 4)], 
[(0, 5), (1, 4, 6), (2, 3)], 
[(0, 5), (2, 3, 4), (1, 6)], 
[(0, 5), (2, 3, 6), (1, 4)], 
[(0, 5), (2, 4, 6), (1, 3)], 
[(0, 5), (3, 4, 6), (1, 2)], 
[(0, 6), (1, 2, 3), (4, 5)], 
[(0, 6), (1, 2, 4), (3, 5)], 
[(0, 6), (1, 2, 5), (3, 4)], 
[(0, 6), (1, 3, 4), (2, 5)], 
[(0, 6), (1, 3, 5), (2, 4)], 
[(0, 6), (1, 4, 5), (2, 3)], 
[(0, 6), (2, 3, 4), (1, 5)], 
[(0, 6), (2, 3, 5), (1, 4)], 
[(0, 6), (2, 4, 5), (1, 3)], 
[(0, 6), (3, 4, 5), (1, 2)], 
[(1, 2), (0, 3, 4), (5, 6)], 
[(1, 2), (0, 3, 5), (4, 6)], 
[(1, 2), (0, 3, 6), (4, 5)], 
[(1, 2), (0, 4, 5), (3, 6)], 
[(1, 2), (0, 4, 6), (3, 5)], 
[(1, 2), (0, 5, 6), (3, 4)], 
[(1, 2), (3, 4, 5), (0, 6)], 
[(1, 2), (3, 4, 6), (0, 5)], 
[(1, 2), (3, 5, 6), (0, 4)], 
[(1, 2), (4, 5, 6), (0, 3)], 
[(1, 3), (0, 2, 4), (5, 6)], 
[(1, 3), (0, 2, 5), (4, 6)], 
[(1, 3), (0, 2, 6), (4, 5)], 
[(1, 3), (0, 4, 5), (2, 6)], 
[(1, 3), (0, 4, 6), (2, 5)], 
[(1, 3), (0, 5, 6), (2, 4)], 
[(1, 3), (2, 4, 5), (0, 6)], 
[(1, 3), (2, 4, 6), (0, 5)], 
[(1, 3), (2, 5, 6), (0, 4)], 
[(1, 3), (4, 5, 6), (0, 2)], 
[(1, 4), (0, 2, 3), (5, 6)], 
[(1, 4), (0, 2, 5), (3, 6)], 
[(1, 4), (0, 2, 6), (3, 5)], 
[(1, 4), (0, 3, 5), (2, 6)], 
[(1, 4), (0, 3, 6), (2, 5)], 
[(1, 4), (0, 5, 6), (2, 3)], 
[(1, 4), (2, 3, 5), (0, 6)], 
[(1, 4), (2, 3, 6), (0, 5)], 
[(1, 4), (2, 5, 6), (0, 3)], 
[(1, 4), (3, 5, 6), (0, 2)], 
[(1, 5), (0, 2, 3), (4, 6)], 
[(1, 5), (0, 2, 4), (3, 6)], 
[(1, 5), (0, 2, 6), (3, 4)], 
[(1, 5), (0, 3, 4), (2, 6)], 
[(1, 5), (0, 3, 6), (2, 4)], 
[(1, 5), (0, 4, 6), (2, 3)], 
[(1, 5), (2, 3, 4), (0, 6)], 
[(1, 5), (2, 3, 6), (0, 4)], 
[(1, 5), (2, 4, 6), (0, 3)], 
[(1, 5), (3, 4, 6), (0, 2)], 
[(1, 6), (0, 2, 3), (4, 5)], 
[(1, 6), (0, 2, 4), (3, 5)], 
[(1, 6), (0, 2, 5), (3, 4)], 
[(1, 6), (0, 3, 4), (2, 5)], 
[(1, 6), (0, 3, 5), (2, 4)], 
[(1, 6), (0, 4, 5), (2, 3)], 
[(1, 6), (2, 3, 4), (0, 5)], 
[(1, 6), (2, 3, 5), (0, 4)], 
[(1, 6), (2, 4, 5), (0, 3)], 
[(1, 6), (3, 4, 5), (0, 2)], 
[(2, 3), (0, 1, 4), (5, 6)], 
[(2, 3), (0, 1, 5), (4, 6)], 
[(2, 3), (0, 1, 6), (4, 5)], 
[(2, 3), (0, 4, 5), (1, 6)], 
[(2, 3), (0, 4, 6), (1, 5)], 
[(2, 3), (0, 5, 6), (1, 4)], 
[(2, 3), (1, 4, 5), (0, 6)], 
[(2, 3), (1, 4, 6), (0, 5)], 
[(2, 3), (1, 5, 6), (0, 4)], 
[(2, 3), (4, 5, 6), (0, 1)], 
[(2, 4), (0, 1, 3), (5, 6)], 
[(2, 4), (0, 1, 5), (3, 6)], 
[(2, 4), (0, 1, 6), (3, 5)], 
[(2, 4), (0, 3, 5), (1, 6)], 
[(2, 4), (0, 3, 6), (1, 5)], 
[(2, 4), (0, 5, 6), (1, 3)], 
[(2, 4), (1, 3, 5), (0, 6)], 
[(2, 4), (1, 3, 6), (0, 5)], 
[(2, 4), (1, 5, 6), (0, 3)], 
[(2, 4), (3, 5, 6), (0, 1)], 
[(2, 5), (0, 1, 3), (4, 6)], 
[(2, 5), (0, 1, 4), (3, 6)], 
[(2, 5), (0, 1, 6), (3, 4)], 
[(2, 5), (0, 3, 4), (1, 6)], 
[(2, 5), (0, 3, 6), (1, 4)], 
[(2, 5), (0, 4, 6), (1, 3)], 
[(2, 5), (1, 3, 4), (0, 6)], 
[(2, 5), (1, 3, 6), (0, 4)], 
[(2, 5), (1, 4, 6), (0, 3)], 
[(2, 5), (3, 4, 6), (0, 1)], 
[(2, 6), (0, 1, 3), (4, 5)], 
[(2, 6), (0, 1, 4), (3, 5)], 
[(2, 6), (0, 1, 5), (3, 4)], 
[(2, 6), (0, 3, 4), (1, 5)], 
[(2, 6), (0, 3, 5), (1, 4)], 
[(2, 6), (0, 4, 5), (1, 3)], 
[(2, 6), (1, 3, 4), (0, 5)], 
[(2, 6), (1, 3, 5), (0, 4)], 
[(2, 6), (1, 4, 5), (0, 3)], 
[(2, 6), (3, 4, 5), (0, 1)], 
[(3, 4), (0, 1, 2), (5, 6)], 
[(3, 4), (0, 1, 5), (2, 6)], 
[(3, 4), (0, 1, 6), (2, 5)], 
[(3, 4), (0, 2, 5), (1, 6)], 
[(3, 4), (0, 2, 6), (1, 5)], 
[(3, 4), (0, 5, 6), (1, 2)], 
[(3, 4), (1, 2, 5), (0, 6)], 
[(3, 4), (1, 2, 6), (0, 5)], 
[(3, 4), (1, 5, 6), (0, 2)], 
[(3, 4), (2, 5, 6), (0, 1)], 
[(3, 5), (0, 1, 2), (4, 6)], 
[(3, 5), (0, 1, 4), (2, 6)], 
[(3, 5), (0, 1, 6), (2, 4)], 
[(3, 5), (0, 2, 4), (1, 6)], 
[(3, 5), (0, 2, 6), (1, 4)], 
[(3, 5), (0, 4, 6), (1, 2)], 
[(3, 5), (1, 2, 4), (0, 6)], 
[(3, 5), (1, 2, 6), (0, 4)], 
[(3, 5), (1, 4, 6), (0, 2)], 
[(3, 5), (2, 4, 6), (0, 1)], 
[(3, 6), (0, 1, 2), (4, 5)], 
[(3, 6), (0, 1, 4), (2, 5)], 
[(3, 6), (0, 1, 5), (2, 4)], 
[(3, 6), (0, 2, 4), (1, 5)], 
[(3, 6), (0, 2, 5), (1, 4)], 
[(3, 6), (0, 4, 5), (1, 2)], 
[(3, 6), (1, 2, 4), (0, 5)], 
[(3, 6), (1, 2, 5), (0, 4)], 
[(3, 6), (1, 4, 5), (0, 2)], 
[(3, 6), (2, 4, 5), (0, 1)], 
[(4, 5), (0, 1, 2), (3, 6)], 
[(4, 5), (0, 1, 3), (2, 6)], 
[(4, 5), (0, 1, 6), (2, 3)], 
[(4, 5), (0, 2, 3), (1, 6)], 
[(4, 5), (0, 2, 6), (1, 3)], 
[(4, 5), (0, 3, 6), (1, 2)], 
[(4, 5), (1, 2, 3), (0, 6)], 
[(4, 5), (1, 2, 6), (0, 3)], 
[(4, 5), (1, 3, 6), (0, 2)], 
[(4, 5), (2, 3, 6), (0, 1)], 
[(4, 6), (0, 1, 2), (3, 5)], 
[(4, 6), (0, 1, 3), (2, 5)], 
[(4, 6), (0, 1, 5), (2, 3)], 
[(4, 6), (0, 2, 3), (1, 5)], 
[(4, 6), (0, 2, 5), (1, 3)], 
[(4, 6), (0, 3, 5), (1, 2)], 
[(4, 6), (1, 2, 3), (0, 5)], 
[(4, 6), (1, 2, 5), (0, 3)], 
[(4, 6), (1, 3, 5), (0, 2)], 
[(4, 6), (2, 3, 5), (0, 1)], 
[(5, 6), (0, 1, 2), (3, 4)], 
[(5, 6), (0, 1, 3), (2, 4)], 
[(5, 6), (0, 1, 4), (2, 3)], 
[(5, 6), (0, 2, 3), (1, 4)], 
[(5, 6), (0, 2, 4), (1, 3)], 
[(5, 6), (0, 3, 4), (1, 2)], 
[(5, 6), (1, 2, 3), (0, 4)], 
[(5, 6), (1, 2, 4), (0, 3)], 
[(5, 6), (1, 3, 4), (0, 2)], 
[(5, 6), (2, 3, 4), (0, 1)]] 

Answer 2

生成排列並刪除重複項。

>>> 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') 

Answer 3

可以解決與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 4

這裏是實現的一個可能的方式：

def permutations(colors, l): 
    if l == 0: 
     yield [] 
    else: 
     for i in range(len(colors)): 
      if colors[i]: 
       la = colors[:i] 
       lb = [colors[i][1:]] 
       lc = colors[i + 1:] 
       choice = colors[i][0] 
       for rest in permutations(la + lb + lc, l - 1): 
        yield [choice] + rest 

用法：

for choice in permutations([['R'] * 2, ['B'] * 2], 4): 
    print(choice) 


['R', 'R', 'B', 'B'] 
['R', 'B', 'R', 'B'] 
['R', 'B', 'B', 'R'] 
['B', 'R', 'R', 'B'] 
['B', 'R', 'B', 'R'] 
['B', 'B', 'R', 'R']