时间戳

首页 > 解决方案 > Julia：具有唯一整数的向量的“n”项的所有可能总和，（重复）

julia - Julia：具有唯一整数的向量的“n”项的所有可能总和，（重复）

问题描述

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

给定 some n，我想获得n集合元素求和的所有可能值，包括将元素与自身求和。重要的是我得到的清单是详尽的。

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

对于给定的、具体的n，我知道如何解决问题。我想要一种简洁的方式来解决任何n.

编辑：这个问题适用于 Julia 0.7 及更高版本...

标签： juliacombinatorics

解决方案

这是一个典型的任务，您可以在递归函数中使用字典（为了清楚起见，我正在注释类型）：

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您在外部递归调用中达到的循环中向量索引的距离，以避免产生重复，这将加快过程。

推荐阅读