You could also use an inner function that closes over the array that you're
pushing onto:
function subsetsum(m::Int, n::Int, w::Array{Int,1}, x::Array{Bool,1},
s::Int, k::Int, r::Int)
result = Array{Int}[]
function inner(s, k, r)
local j::Int = 0
x[k] = true
if s + w[k] == m
push!(result, w[find(x[1:k])])
else
if s + w[k] + w[k+1] <= m
inner(s+w[k], k+1, r-w[k])
end
end
if s + r - w[k] >= m && s + w[k+1] <= m
x[k] = false
inner(s, k+1, r-w[k])
end
end
inner(s, k, r)
return result
end
This way, you only need to pass the arguments that are changing to the
recursive calls.
On Wednesday, June 25, 2014 8:27:18 AM UTC-4, Mauro wrote:
>
> Could you pass a storage array to the function? Like so:
>
> function subsetsum(m::Int, n::Int, w::Array{Int,1}, x::Array{Bool,1},
> s::Int, k::Int, r::Int, sol::Array{Bool,1})
> local j::Int = 0
> x[k] = true
> if s + w[k] == m
> push!(sol, 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], sol)
> 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], sol)
> end
> end
>
> > *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
>
> I think there are three approaches:
> - do as you did/above
> - if you have an idea of the number of solutions, use
> `sizehint(sol, numsols)`. Or do sizehints in big junks.
> - run the computation twice, once to compute the number of solutions,
> the second time around to fill the `sol` array.
>
> No idea which one is fastest.
>
