朱莉娅：具有唯一整数的 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 的索引有多远，以避免产生重复项，这将加快过程。

Answer 2

I want a concise way of being able to solve it for any n.

这是一个简洁的解决方案，使用IterTools.jl:

茱莉亚 0.6

using IterTools
n = 3
summands = [1, 2, 6, 4]
myresult = map(x -> (sum(x), x), reduce((x1, x2) -> vcat(x1, collect(product(fill(summands, x2)...))), [], 1:n))

（IterTools.jl 是 product() 所必需的）

茱莉亚 0.7

using Iterators
n = 3
summands = [1, 2, 6, 4]
map(x -> (sum(x), x), reduce((x1, x2) -> vcat(x1, vec(collect(product(fill(summands, x2)...)))), 1:n; init = Vector{Tuple{Int, NTuple{n, Int}}}[]))

(在 Julia 0.7 中，中性元素的参数位置从第 2 个参数变为第 3 个参数。)

这是如何工作的？

一行缩进（使用Julia 0.6版本，Julia 0.7版本思路相同）：

map(
  # Map the possible combinations of `1:n` entries of `summands` to a tuple containing their sum and the summands used.
  x -> (sum(x), x),
  # Generate all possible combinations of `1:n`summands of `summands`.
  reduce(
                # Concatenate previously generated combinations with the new ones
    (x1, x2) -> vcat(
                    x1,
                    vec(
                        collect(
                            # Cartesian product of all arguments.
                            product(
                                # Use `summands` for `x2` arguments. 
                                fill(
                                    summands,
                                    x2)...)))),
  # Specify for what lengths we want to generate combinations.
  1:n;
  # Neutral element (empty array).
  init = Vector{Tuple{Int, NTuple{n, Int}}}[]))

Answer 3

茱莉亚 0.6

这真的只是为了让专家免费批评为什么我的方法不如他们的！

using Combinatorics, BenchmarkTools

function nsum(a::Vector{Int}, n::Int)::Vector{Tuple{Int, Vector{Int}}}
    r = Vector{Tuple{Int, Vector{Int}}}()
    s = with_replacement_combinations(a, n)
    for i in s
        push!(r, (sum(i), i))
    end
    return sort!(r, by = x -> x[1])
end

@btime nsum([1, 2, 6, 4], 3)

它在我的 n = 3 的 1.8 GHz 处理器上运行大约 4.154 微秒。它生成一个排序数组，显示总和（可能出现不止一次）及其组成方式（对于总和的每个实例都是唯一的）。

朱莉娅：具有唯一整数的 Vector 的“n”项的所有可能总和，（重复）

Julia: All possible sums of `n` entries of a Vector with unique integers, (with repetition)

combinatorics

julia

茱莉亚 0.6

茱莉亚 0.7

这是如何工作的？