Python“星条旗”

Question

我试图找到所有可能的方法在 k 个孩子之间分发 n 个糖果。例如，根据星条形公式，在 5 个孩子之间分配 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 生成此列表的速度如此之慢？我错过了什么？

Answer 1

我看到你的数学有两个问题。首先，你在那里描述一个组合。实际上，您正在考虑（96 选择 5），这并未涵盖所有排列。其次，排列实际上是 96!/91!，比约 400 万高几个数量级。只需添加字节数，您现在就处于高 GB的内存使用范围内，这可以解释为什么您的机器变慢了；仅由此产生的内存使用量就可以粉碎大多数现代消费机器。