Julia实现n的k分拆（无排列重复）问题求助

你的partition函数当前会生成带排列重复的分拆结果，比如[4,0,0]和[0,4,0]这类属于同一分拆的重复项。要得到你期望的无重复结果，可通过以下两种方式实现：

方法一：基于现有代码修改（排序去重） #

对每个计数数组按降序排序后，用unique去除重复项，就能得到唯一的分拆结果：

using Combinatorics  # 需先导入该包

function partition(n, k)
    p = with_replacement_combinations(1:n, k)
    counts = map(A -> [sum(A .== i) for i in 1:n], p)
    # 对计数数组降序排序后去重
    unique(sort.(counts, rev=true))
end

调用partition(3,4)会输出：

4-element Vector{Vector{Int64}}:
 [4, 0, 0]
 [3, 1, 0]
 [2, 2, 0]
 [2, 1, 1]

方法二：直接生成非递增分拆（更高效） #

如果n和k数值较大，方法一的去重操作会有性能损耗。可以直接生成符合要求的分拆：先生成k的分拆（部分数不超过n），再补零到n个元素并保持降序：

using Combinatorics

function partition(n, k)
    # 生成k的所有分拆，限制分拆部分数不超过n
    parts = partitions(k, n)
    # 给每个分拆补零至长度n，保持降序
    map(p -> vcat(p, zeros(Int, n - length(p))), parts)
end

该方法无需去重，执行效率更高，输出结果与预期一致。

内容的提问来源于stack exchange，提问作者A. T