On Monday, October 19, 2015 at 7:39:03 AM UTC-4, Patrick Useldinger wrote:
>
> Hello
> true but no summand may appear twice, and only numbers 1 to 9 may be used.
> For example, (10, 3) yields
>
> Array[Int16[2,3,5],Int16[1,4,5],Int16[1,3,6],Int16[1,2,7]]
>
> Regards,
> -Patrick
>
Ah, okay, I missed those constraints. I think you could probably adapt the
partitions code to generate only partitions that satisfy that constraint,
but an alternative is just to filter combinations of 1:9 according to
whether they have the correct sum.
julia> function decompose(val, num)
out = Vector{Int}[]
for c in combinations(1:9, num)
if sum(c) == val
push!(out, c)
end
end
out
end
julia> function benchmark()
local maxres = Int[]
for i in 1:45
for j in 2:20
res = decompose(i, j)
if length(res) > length(maxres)
maxres = res
end
end
end
maxres
end
julia> benchmark(); @time benchmark()
0.002602 seconds (70.52 k allocations: 5.409 MB)
12-element Array{Array{Int64,1},1}:
[1,2,8,9]
[1,3,7,9]
[1,4,6,9]
[1,4,7,8]
[1,5,6,8]
[2,3,6,9]
[2,3,7,8]
[2,4,5,9]
[2,4,6,8]
[2,5,6,7]
[3,4,5,8]
[3,4,6,7]
3ms is pretty snappy compared to the recursive solutions.
