Julia:具有唯一整数的 Vector 的 `n` 条目的所有可能总和(有重复)

Question

假设我有一个唯一整数向量，例如 [1, 2, 6, 4] (排序并不重要)。

给定一些 n，我想获得对集合中的 n 个元素求和的所有可能值，包括将一个元素与其自身求和。重要的是我得到的列表详尽。

例如，对于n = 1，我得到原始集合。 对于 n = 2 ，我应该得到 1 与所有其他元素相加的所有值，2 与所有其他元素相加的所有值，等等。还需要某种内存，从某种意义上说，我必须知道来自哪些条目原来的集合是我所面临的总和的来源。

对于给定的特定n，我知道如何解决问题。我想要一种能够解决任何 n 问题的简洁方法。

编辑:这个问题适用于 Julia 0.7 及以上版本...

Answer 1

这是一个典型的任务，您可以在递归函数中使用字典(为了清楚起见，我对类型进行了注释):

function nsum!(x::Vector{Int}, n::Int, d=Dict{Int,Set{Vector{Int}}},
               prefix::Vector{Int}=Int[])
    if n == 1
        for v in x
            seq = [prefix; v]
            s = sum(seq)
            if haskey(d, s)
                push!(d[s], sort!(seq))
            else
                d[s] = Set([sort!(seq)])
            end
        end
    else
        for v in x
            nsum!(x, n-1, d, [prefix; v])
        end
    end
end

function genres(x::Vector{Int}, n::Int)
    n < 1 && error("n must be positive")
    d = Dict{Int, Set{Vector{Int}}}()
    nsum!(x, n, d)
    d
end

现在您可以使用它了，例如

julia> genres([1, 2, 4, 6], 3)
Dict{Int64,Set{Array{Int64,1}}} with 14 entries:
  16 => Set(Array{Int64,1}[[4, 6, 6]])
  11 => Set(Array{Int64,1}[[1, 4, 6]])
  7  => Set(Array{Int64,1}[[1, 2, 4]])
  9  => Set(Array{Int64,1}[[1, 4, 4], [1, 2, 6]])
  10 => Set(Array{Int64,1}[[2, 4, 4], [2, 2, 6]])
  8  => Set(Array{Int64,1}[[2, 2, 4], [1, 1, 6]])
  6  => Set(Array{Int64,1}[[2, 2, 2], [1, 1, 4]])
  4  => Set(Array{Int64,1}[[1, 1, 2]])
  3  => Set(Array{Int64,1}[[1, 1, 1]])
  5  => Set(Array{Int64,1}[[1, 2, 2]])
  13 => Set(Array{Int64,1}[[1, 6, 6]])
  14 => Set(Array{Int64,1}[[4, 4, 6], [2, 6, 6]])
  12 => Set(Array{Int64,1}[[4, 4, 4], [2, 4, 6]])
  18 => Set(Array{Int64,1}[[6, 6, 6]])

编辑:在代码中，我使用 sort! 和 Set 来避免重复条目(如果需要重复，请删除它们)。此外，您还可以跟踪在外部递归调用中到达的循环中向量 x 上的索引有多远，以避免生成重复项，这将加快该过程。