我正在尝试寻找所有可能的方法来向 k 个 child 分发 n 颗糖果。
例如,根据星条公式,向 5 个 child 分发 96 颗糖果的方式有 100 种!/(96!*4!) = 3 921 225
大小为 5 的所有可能排列的元组。
list2 = [item for item in it.product(range(97), repeat = 5)
if sum(item) == 96]
我的电脑似乎因复杂性而不堪重负。
每个元组消耗 24*5 = 120 字节的内存。这导致 921 225 * 120 = 470547000
字节或 450 mb。看起来没那么多。为什么 PC 生成此列表的速度如此之慢?我错过了什么?
最佳答案
这是使您的方法发挥作用的一种方法。它使用itertools.combinations。构建完整列表需要几秒钟的时间。如需更快的基于 numpy
的方法,请参阅本文底部。
它的工作原理是枚举 1 到 100 之间的四个条形的所有组合,始终添加外部条形 0 和 101。五个 child 的分配就是条形之间的值,即条形的差异减一。
import numpy as np
import itertools
bars = [0, 0, 0, 0, 0, 101]
result = [[bars[j+1] - bars[j] - 1 for j in range(5)] for bars[1:-1] in itertools.combinations(range(1, 101), 4)]
# sanity check
len(result)
# 3921225
# show few samples
from pprint import pprint
pprint(result[::400000])
# [[0, 0, 0, 0, 96],
# [2, 26, 12, 8, 48],
# [5, 17, 22, 7, 45],
# [8, 23, 30, 16, 19],
# [12, 2, 73, 9, 0],
# [16, 2, 25, 40, 13],
# [20, 29, 24, 0, 23],
# [26, 13, 34, 14, 9],
# [33, 50, 4, 5, 4],
# [45, 21, 26, 1, 3]]
为什么你的效果不太好?我认为主要是因为你的循环有点浪费,97^5 比 100 选择 4 大很多。
如果您想要速度非常快,可以将 itertools.combinations
替换为 numpy
版本:
https://stackoverflow.com/a/42202157/7207392
def fast_comb(n, k):
a = np.ones((k, n-k+1), dtype=int)
a[0] = np.arange(n-k+1)
for j in range(1, k):
reps = (n-k+j) - a[j-1]
a = np.repeat(a, reps, axis=1)
ind = np.add.accumulate(reps)
a[j, ind[:-1]] = 1-reps[1:]
a[j, 0] = j
a[j] = np.add.accumulate(a[j])
return a
fb = fast_comb(100, 4)
sb = np.empty((6, fb.shape[1]), int)
sb[0], sb[1:5], sb[5] = -1, fb, 100
result = np.diff(sb.T) - 1
result.shape
# (3921225, 5)
result[::400000]
# array([[ 0, 0, 0, 0, 96],
# [ 2, 26, 12, 8, 48],
# [ 5, 17, 22, 7, 45],
# [ 8, 23, 30, 16, 19],
# [12, 2, 73, 9, 0],
# [16, 2, 25, 40, 13],
# [20, 29, 24, 0, 23],
# [26, 13, 34, 14, 9],
# [33, 50, 4, 5, 4],
# [45, 21, 26, 1, 3]])
这大约需要一秒钟。
关于 python "Stars and Bars",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53561814/