如何找出和为n的k个正整数的所有排列型分拆？

我们需要找出所有由k个正整数组成、和为n的分拆（包含所有排列形式）。比如当k=4、n=6时，基础分拆为：

1 + 1 + 1 + 3 = 6
1 + 1 + 2 + 2 = 6

每个基础分拆的所有排列都要纳入结果，比如[1,1,1,3]有4种排列，[1,1,2,2]有6种排列，最终结果共10种。

Julia 优化实现 #

原代码先生成全排列再去重，存在大量冗余计算。改用multiset_permutations可直接生成每个基础分拆的唯一排列，效率大幅提升：

using Combinatorics
n, k = 6, 4
result = []
for part in partitions(n, k)
    append!(result, multiset_permutations(part))
end
# 可选：确保结果无重复（multiset_permutations已保证唯一，此步可省略）
result = unique(result)

Python 实现 #

方案1：依赖sympy（高效） #

利用multiset_permutations直接生成唯一排列：

from sympy.utilities.iterables import multiset_permutations
from itertools import combinations_with_replacement

n, k = 6, 4
result = []

# 生成所有非降序的基础分拆（k个正整数和为n）
for combo in combinations_with_replacement(range(1, n - k + 2), k):
    if sum(combo) == n:
        result.extend(multiset_permutations(combo))

# 转换为列表并去重（基础分拆唯一时此步可简化）
result = [list(p) for p in set(tuple(p) for p in result)]

方案2：不依赖第三方库（兼容性好） #

用combinations_with_replacement生成基础分拆，结合集合自动去重排列：

from itertools import combinations_with_replacement, permutations

n, k = 6, 4
result_set = set()

for combo in combinations_with_replacement(range(1, n - k + 2), k):
    if sum(combo) == n:
        for p in permutations(combo):
            result_set.add(p)

result = list(result_set)

优化思路 #

先找到非降序的基础分拆（避免重复处理相同结构的分拆），再对每个基础分拆生成其所有唯一排列，从根源减少冗余计算，比先生成全排列再去重的效率高得多。

内容的提问来源于stack exchange，提问作者zdm