gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 08:29:31 24 4
gpt4 key购买 nike

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

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

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

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

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

最佳答案

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

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 上的索引有多远,以避免生成重复项,这将加快该过程。

关于Julia:具有唯一整数的 Vector 的 `n` 条目的所有可能总和(有重复),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51338487/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com