[Solved]: Filling Rows of a Matrix Subject to Conditions

Problem Detail: 

I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that:

• The sum of values in any row is N
• No rows are repeated (this should ensure that every such possibility is listed)

For example, with N=2, we have 10 (=3*4*5/6) rows:

2 0  0 0 1 1  0 0 0 2  0 0 1 0  1 0 1 0  0 1 0 1  1 0 0 1  0 1 0 0  2 0 0 0  1 1  0 0  0 2 

I've been trying for a while to program this (in R, for what it's worth), but I'm struggling to get anywhere. Any advice?

Asked By : lokodiz

Answered By : Dukeling

Below is some pseudo-code to generate the rows.

It basically uses recursion as follows:

• Try all values up to the remaining total in the current cell.
• Recurse onto the next cell.

Pseudo-code:

// (N+1)*(N+2)*(N+3)/6 is a lot array[2*N]  // What you'll call printRows(N)    printRows(N, 1)  printRows(N, pos)    if pos == array.length + 1       // reached the bottom-most recursion call       // we don't really have a choice of value here since we need to get to N       //   and only have the current value left       array[array.length] = N       print array    else       for i = N; i >= 0; i--          array[pos] = i          printRows(N-i, pos+1) 

Calling printRows(2) will print:

[2, 0, 0, 0] [1, 1, 0, 0] [1, 0, 1, 0] [1, 0, 0, 1] [0, 2, 0, 0] [0, 1, 1, 0] [0, 1, 0, 1] [0, 0, 2, 0] [0, 0, 1, 1] [0, 0, 0, 2] 

Java test.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13562