An algorithm for finding all possible binary combinations with the condition

Question

Here is one of them - for you a mathematical brain. I have a matrix, in fact its half matrix, cut diagonally. Each matrix element can be 1 or 0 . I need to find all possible combinations of 1 s and 0 s for any matrix of width N.

It is quite simple, you can get the number of elements on this matrix with a given width N with for this example, where N = 7 this will give us 28 or the number of elements. Then you can get combinations with .

So the formula will be to get all possible combinations.

Now that's where it gets complicated. There is one condition that must be met for each result. The sum of each set of elements on the matrix (shown below with each row presented) should be less than 4 for the first set (first in the first row), less than 3 for all other sets (these are constants, regardless of the value of N).

Here's what the sets look like for this example ( N = 7 ). If you notice that each line is represented. So, for the first set, if the combination is 0 1 0 1 0 1 0 , this would be true, since its sum is <4 (starting from its first line). For the second set, if the combination is 1 0 0 0 0 1 0 , it is valid because it must be <3.

I need to do this for huge matrices, so coarse forcing all possible permutations to find those that fall under this condition would be unreasonable. I need to find some kind of algorithm that I can use to create valid matrices from bottom to top, and not from top to bottom. Perhaps separate operations that can be compiled later to give a complete set of results.

Any ideas are welcome.

Answer 1

A simple algorithm that recursively generates each solution:

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 other than a file, but watch out for memory consumption.

Answer 2

Here is a basic idea to get started; but too big for a comment, but not a complete answer.

The idea is to start with the most "filled" matrix, and not empty, and then fill it.

Basic Bandwidth Removal Procedure

Start with a matrix filled with all rows filled up to their maximum number of 1 s, i.e. row 0 has 4 1 , and the rest of the rows have 3 1 s. Then start checking the conditions. Condition 0 (line 0) is satisfied automatically. For the remaining conditions, either they are satisfied, or too many 1 in their set condition: select 1 until the condition is met. Do it for all conditions.

Making all the "simpler"

By doing this, you get a matrix that satisfies all the conditions. Now you can change any 1 to 0 , and the matrix will still satisfy all conditions. So, as soon as you have the “maximum” solution, you can generate all its solutions trivially.