Help getting matrix combinations that sum to X

General Usage
1

I am trying to find all possible combinations of a matrix where the values sum to some target. It seems rather straightforward but the solution does elude me at the moment. Here is an example matrix. In this example, I’d like to find all possible matrix positions where the sum is 100. A “position” is taking one value from each column. So, trivially I can get that ((1,1),(5,2),(5,3),(5,4),(5,5)) and those like it are possible combinations. But finding all of them is escaping me…

Would anyone be willing to help?

julia> N = 5
5

julia> L = 5
5

julia> spots = repeat(reverse(collect(range(0,100,length=L))),1,N)
5×5 Array{Float64,2}:
 100.0  100.0  100.0  100.0  100.0
  75.0   75.0   75.0   75.0   75.0
  50.0   50.0   50.0   50.0   50.0
  25.0   25.0   25.0   25.0   25.0
   0.0    0.0    0.0    0.0    0.0
2

The problem statement isn’t clear to me. What is a “combination of a matrix”? Likewise can you clarify what “A ‘position’ is taking one value from each column” means?

3

More concretely, find all possible i_1,...,i_N in ((i_1,1),(i_2,2),...,(i_N,N)) (in this particular case, a collection of 5 cartesian indices) such that the sum of the values at those spots in matrix equals 100.

So the example from the first post is “trivial” because the sum of ((1,1),(5,2),(5,3),(5,4),(5,5)) is 100 + 0 + 0 + 0 + 0.

Another possibility is ((4,1),(4,2),(4,3),(4,4),(5,5)) which sums to 25 + 25 + 25 + 25 + 0.

The columns are always going to be identical, if that helps.

4

I believe that this code will solve your problem:

using Combinatorics

L = 5
N = 5
spots = repeat(reverse(collect(range(0,stop=100,length=L))),1,N)

linear_inds = []
for n in 1:N^2
    combs = combinations(1:N^2,n)
    for comb in combs
        if sum(spots[comb]) == 100
            push!(linear_inds,comb)
        end
    end
end
# Check that the linear indices have the desired propoerty.
for i in 1:length(linear_inds)
    @assert sum(spots[linear_inds[i]]) == 100
end

If you want to convert the linear indices back into cartesian indices, then you can use this:

CartesianIndices(spots)[linear_inds[1][1]]

I only just noticed that you said that the columns will always be the same. I think that based on the above you could exploit that property to get a speed boost. In fact, there are a lot of changes that you could make to improve speed.

1 Like