Algorithm to find all possible binary combinations with a condition

Question

Here is one is for you math brains out there. I have a matrix, actually its half a matrix, cut diagonally. Each element of the matrix can be a 1 or a 0. I need to find all the possible combinations of 1s and 0s for any matrix of width N.

This is easy enough, you can get the number of elements on this matrix given width N with for this example where N=7 this would give us 28 or the number of elements. Then you can get the combinations with .

So the formula would be to get all the possible combinations.

Now here is where it gets tricky. There is one condition that must hold true for each result. The sum of the each set of elements on the matrix (shown below with each row represented) must be less than 4 for the first set (the one on the first row), less than 3 for all the other sets (these are constants regardless of the N value).

Here are what the sets for this example (N=7) look like. If you notice each row is represented. So for the first set if the combination is 0 1 0 1 0 1 0 this would be valid as its sum is < 4 (since its the first row). For the second set if the combination is 1 0 0 0 0 1 0 it is valid as it needs to be < 3.

I need to do this for huge matrices so brute forcing all possible permutations to find the ones that fall under this condition would be unfeasable. I need to find some sort of algorithm I can use to generate the valid matrices bottom up rather than top down. Maybe doing separate operations that can be composed later to yield a total set of results.

Any and all ideas are welcome.

Answer 1

A simple algorithm generating each solution recursively :

global File //A file where you will store your data
global N    //Your matrix size

//matrix contains the matrix we build (int[][])
//set contains the number of 1 we can use on a set (int[])
//c is the column number (int)
//r is the row number (int)
function f ( matrix, set, c, r ) :
  if ( c == N ):
    r = r + 1
    c = r

  if ( r == N ):
    write ( matrix in File )
    // Implement your own way of storing the matrix

  if ( set[r] > 0 AND (c+2 < N AND set[c+2] > 0) ):
    matrix[c][r] = 1
    set[c]--
    set[r]--
    f ( matrix, set, c+1, r )

  matrix[c][r] = 0
  f ( matrix, set, c+1, r)
end

//Calling our function with N = 5
N = 5
f([[0,0,0,0,0],[0,0,0,0,0],...], [3,2,2,2,2], 0, 0)

You can store each matrix in something else than a file but keep an eye on your memory consumption.