6

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 formula for this example where N=7 this would give us 28 or the number of elements. Then you can get the combinations with formula.

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

empty

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).

enter image description here

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.

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

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.

Improve this question
13
  • Your condition doesn't seem clear enough. Could you elaborate more or give clear example? Commented Sep 16, 2015 at 5:09
  • Do you mean N+1 instead of N1 in the term for the number of elements in the matrix? Commented Sep 16, 2015 at 6:11
  • What do you mean by huge matrices? Can you tell limit of n? Commented Sep 16, 2015 at 6:21
  • And according to your design here, there is no way the 4 corner elements would fall in any category. Am I correct? Commented Sep 16, 2015 at 6:22
  • @Codor, correct N+1, the + got lost on the api used to render the formulas. Fixed it. Commented Sep 16, 2015 at 7:16

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I like this idea. I haven't checked your pseudo-code, but the idea behind it lets you systematically generate all possible solutions, by 'allocating' 1s from two 'budgets': only if both budgets (here: set) have a 1 available can you allocate it in the matrix.
0

Here's a basic idea to get started; it's too large for a comment, though, but not a complete answer.

The idea is to start with a maximally 'filled' matrix rather than an empty one and then filling it.

Basic striping away procedure

Start with a matrix filled with all rows filled to their maximum number of 1s, that is row 0 has 4 1s and the other rows each have 3 1s. Then, start checking the conditions. Condition 0 (row 0) is automatically satisfied. For the rest of the conditions, either they are satisfied, or there are too many 1s in its condition set: take away 1s until the condition is satisfied. Do this for all conditions.

Generating all 'simpler' ones

Doing this, you end up with a matrix that satisfies all conditions. Now, you can change any 1 to a 0 and the matrix will still satisfy all the conditions. So, once you have a 'maximal' solution, you can generate all sub-solutions of it trivially.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.