python - 每种方式来组织M个列表槽中的N个对象

我试图找到一种方法，使用内置函数，列出每种方法来组织N插槽中的M球。球可以堆在槽里。例如：
N=2，M=3->{0 | 1 |，1 | 0 | 1 |，1 | 1 | 0 |，2 | 0 |，0 |，2 |，0 |，0 | 2 |，0 |，0 | 2 |
itertools.permutations()是谜题的一部分，但是你怎么能通过所有可能的球堆来保持N？

最佳答案

让oo代表两个球。
在3个槽中放置2个球的问题等同于在2个杆周围放置2个球的问题：

|o|o   -->  0,1,1
o||o        1,0,1
o|o|        1,1,0
oo||        2,0,0
|oo|        0,2,0
||oo        0,0,2

棍子，|代表槽的边缘。右边显示了每个插槽中的球数。
请注意，每排有4个位置和2根棍子。总有一根棍子比槽少。所以这个问题相当于找到所有的方法，从4种可能性中选择2个球的位置。4选择2。

In [98]: import itertools as IT

In [99]: list(IT.combinations(range(4), 2))
Out[99]: [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

因此，这些是球可能的位置。
剩下要做的就是计算这些球属于哪个槽。以（1，3）为例。（1，3）的图解如下：

|o|o

结果是，如果从（1，3）中减去（0，1）个元素，就得到了每个球的槽：

(1, 3)
(0, 1)
------
(1, 2)

因此，第一个球在槽1，第二个在槽2。
一般来说，如果从组合中减去range(m-1)，就得到了时隙值。如果你把你要减去的数量看作是图形中当前球之前的球数，这就有一定的意义。因为我们的图表由球和槽组成，如果你减去球，剩下的就是槽。

import itertools as IT
def pigeonhole(n, m):
    """
    Generate the ways n balls can placed in m slots
    """
    for choice in IT.combinations(range(n+m-1), n):
        slot = [c-i for i,c in enumerate(choice)]
        result = [0]*m
        for i in slot:
            result[i] += 1
        yield result

print(list(pigeonhole(2,3)))

产量

[[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]