如何高效计算最多X组中选择Y个项目的方法数？

Question

我不知道如何简洁地描述这一点。假设您有 X 组物品，同一组中的每个物品都是相同的。所有组的大小都是无限的。

您想从 X 组中完全随机选择 Y 项，您想要恰好 Y 项，并且您可以从 1 组、2 组、3 组...所有组中选择全部。

我很难描述，所以我举一个简单的例子。假设您想从 3 组中选择 9 个项目，将这些组称为 A、B、C。

您可以选择（9A，0B，0C）或（0A，9B，0C）或（0A，0B，9C）或（1A，2B，6C）...

您可以从一组、两组或所有组中进行选择。

任务是找到划分 Y 个项目的不同方法的数量，或者来自同一组的项目计数的集合，并且组合并不重要。

说得更清楚一点，(9A, 0B, 0C) 和 (0A, 9B, 0C) 和 (0A, 0B, 9C) 是一样对待的，它们都算 (0, 0, 9) 并且有 3 个获得 (0, 0, 9) 的方法，获得 (0, 1, 8) 的 54 种方法。

我尝试用聪明的方式做到这一点，但我得到了错误的结果：

from collections import Counter
from itertools import product

groups = Counter()
for i in range(10):
    for k in range(j := 9 - i):
        groups[tuple(sorted((i, k, j - k)))] += 1

Counter({(1, 2, 6): 6,
         (1, 3, 5): 6,
         (2, 3, 4): 6,
         (0, 1, 8): 4,
         (0, 2, 7): 4,
         (0, 3, 6): 4,
         (0, 4, 5): 4,
         (1, 1, 7): 3,
         (1, 4, 4): 3,
         (2, 2, 5): 3,
         (0, 0, 9): 1,
         (3, 3, 3): 1})

所以我用蛮力的方式做到了，并迭代所有可能性以获得正确的结果：

new_groups = Counter()
for item in product('abc', repeat=9):
    a = b = c = 0
    for e in item:
        if e == 'a':
            a += 1
        elif e == 'b':
            b += 1
        else:
            c += 1
    new_groups[tuple(sorted((a, b, c)))] += 1

Counter({(2, 3, 4): 7560,
         (1, 3, 5): 3024,
         (2, 2, 5): 2268,
         (1, 4, 4): 1890,
         (3, 3, 3): 1680,
         (1, 2, 6): 1512,
         (0, 4, 5): 756,
         (0, 3, 6): 504,
         (0, 2, 7): 216,
         (1, 1, 7): 216,
         (0, 1, 8): 54,
         (0, 0, 9): 3})

结果是正确的，但是这个方法效率极低，它是指数时间的，对于9个项目3组需要19683次迭代，而9个项目4组需要262144次迭代！

有什么更好的方法？

Answer 1

这是星星和酒吧问题。

总和为 9 的非负整数三元组的个数为 ((3,9)) = (3+9-1 选择 9) = (11 选择 9) = (11 选择 2) = 55。

更一般地，总和为 n 的非负整数 k 元组的数量为 ((k,n)) = (n+k-1 选择 n)。

from math import comb

def number_of_ways_to_choose_n_items_from_k_groups(k, n):
    return comb(n+k-1, n)