I realized a classical version of a* subsetsum algorithm* that not return
just one, but *all* solutions to this problem. I did implement this in R
and Matlab before, but neither of them was fast enough to return solutions
for even small problems in any acceptable time frame. So I was quite happy
to finally see in Julia all solutions for some of the test problems I had
in mind.
Here m is the target integer, w a vector of integer weights; we want to
find all combinations of indices i1,...,ik such that sum(w[[i1,...,ik]])
= m.
n shall be the length of w, and x a boolean vector of length n.
function subsetsum(m::Int, n::Int, w::Array{Int,1}, x::Array{Bool,1},
s::Int, k::Int, r::Int)
local j::Int = 0
x[k] = true
if s + w[k] == m
println(w[find(x[1:k])])
else
if s + w[k] + w[k+1] <= m
subsetsum(m, n, w, x, s+w[k], k+1, r-w[k])
end
end
if s + r - w[k] >= m && s + w[k+1] <= m
x[k] = false
subsetsum(m, n, w, x, s, k+1, r-w[k])
end
end
There is a recursive call and the starting point should be with s = 0; k =
1; and r = sum(w).
As an example, find all tuples of odd squares that sum up to 2014:
julia> m = 2014
julia> w = Int64[u^2 for u in 1:2:isqrt(m)]
julia> n = length(w)
julia> x = fill(false, n)
julia> subsetsum(m, n, w, x, 0, 1, sum(w))
[1,9,25,49,81,1849]
[1,9,25,49,841,1089]
...
[81,121,169,361,441,841]
[169,225,289,361,441,529]
*The problem is*: Solutions found are printed to the console.
Of course, I would like to store all solutions, for instance in a Boolean
array of size k x n where k is the number of solutions.
I managed to do this with a global array X but I assume this will make
the algorithm considerably slower because
1. as I learned here, usage of globals slows Julia down
2. it is unknown how many solutions there are, so the array will have to
grow
Printing to the command line the function takes about 0.0125 secs,
when instead of printing assigning it to another variable it takes 0.00030
secs,
and using a global variable it takes 0.00065 secs -- which is still not bad
for the example above.
*What is a better way to handle intermediate results from recursive
function calls?* Thanks
