如何高效计算将Y个物品分配到X个组的各类组合数？

问题描述 #

现有X组物品，每组内物品完全相同且数量无限。需选取恰好Y个物品，可从1至X组中选取，要求得到所有无序的物品数量分配集合（如(0,0,9)这类排序后的元组）及其对应的出现次数。

该问题等价于：将Y个球随机放入X个容器中，求所有容器内球数的无序集合及对应出现次数，需输出与暴力法完全一致的结果，而非单一统计数值。

目前暴力枚举法结果正确但时间复杂度为指数级（如9个物品3个组需19683次迭代），尝试的优化方法结果错误，现寻求更高效的实现方案。

错误代码示例 #

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

正确但低效的暴力代码示例 #

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

高效实现方案 #

核心思路 #

1. 生成无序划分：先生成所有满足x₁+x₂+…+xₓ=Y的非负整数无序元组（排序为非递减形式，作为唯一标识），这类元组的数量远小于暴力枚举的次数。
2. 计算出现次数：对每个无序元组，通过组合数学公式计算其对应的总出现次数：
   • 多重排列数：该无序元组能生成多少种有序的容器分配方案（考虑重复元素的排列）。
   • 多项式系数：每种有序分配方案在暴力法中的出现次数（即从Y个位置中分配对应数量物品的组合数）。
   • 总次数 = 多重排列数 × 多项式系数。

代码实现 #

from collections import Counter
import math
from itertools import combinations_with_replacement

def get_unordered_distributions(group_count, item_count):
    # 生成所有满足和为item_count的group_count个非负整数无序组合（非递减排序）
    distributions = []
    for combo in combinations_with_replacement(range(item_count + 1), group_count):
        if sum(combo) == item_count:
            distributions.append(tuple(sorted(combo)))
    # 去重（combinations_with_replacement生成的已无重复，此步可选）
    distributions = list(set(distributions))
    
    fact = math.factorial
    result = Counter()
    
    for dist in distributions:
        # 计算多重排列数：group_count! / (各数字出现次数的阶乘乘积)
        count_stats = Counter(dist)
        permutation_num = fact(group_count)
        for cnt in count_stats.values():
            permutation_num //= fact(cnt)
        
        # 计算多项式系数：item_count! / (各元素阶乘的乘积)
        poly_coefficient = fact(item_count)
        for num in dist:
            poly_coefficient //= fact(num)
        
        # 总出现次数
        total = permutation_num * poly_coefficient
        result[dist] = total
    
    # 按出现次数降序排序
    return Counter(sorted(result.items(), key=lambda x: -x[1]))

# 测试示例：3组物品，选9个
print(get_unordered_distributions(3, 9))

优势说明 #

该方法的时间复杂度取决于生成无序划分的数量，对于X=3、Y=9的场景仅需处理12种划分，相比暴力法的19683次迭代，效率提升极为显著。对于更大的X和Y，效率优势会更加明显。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος