Filling Rows of a Matrix Subject to Conditions

Question

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?

Answer 1

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.

Answer 2

If you are allowed to repeat rows, then a simple solution is to repeat the row $(N,0,0,0)$ as many times as needed.

If you are not allowed to repeat rows, this should also be pretty easy to solve. This sounds like an exercise where you learn by doing, so I don't want to spoil it by giving away the answer, but I'll give you some tips and suggestions that will help you develop an answer:

1. What are the requirements for a row to be valid? If $(w,x,y,z)$ are the four numbers in a row, what are the requirements on $w,x,y,z$ for this row to be allowable?

2. If I have one candidate row that meets all the requirements, and another candidate row that also meets all the requirements, can I put the first one in the first row of the matrix and the second row of the matrix? Will that always be valid, or are there any constraints where my choice of the first row of the matrix restricts what I'm allowed to put in the second row of the matrix? (If there are any restrictions, make sure you understand and can state precisely exactly what they are.)

3. How many possible ways are there to choose a single row that meets all of the requirements? Hint: this is a standard problem in combinatorics/counting. If you are in a computer science-oriented course on counting, your textbook will probably include a worked-out problem where it shows how to count the number of ways to place $k$ balls into $n$ bins with replacement, when order does not matter. Make sure you understand the solution to that -- you might find it helpful.

4. How many different rows do you need? Compare this to your answer to #2 above. Relevance: If you need more rows than there are possibilities, and you need them to all be different, you're hosed. If there are more possibilities than you need to list in your matrix, you can pick any subset.

5. How would you enumerate all valid rows? You probably want to use some nested loops, e.g., loop over some range of values of $w$, and for each such $w$, loop over some range of values of $x$, and so on. What range of values should you use for $w$? (What values of $w$ are allowable?) What range of values should you use for $x$? (Since this is a nested loop, your range of values for $x$ is allowed to depend upon $w$.) Fill out the rest of the details.

   Update: Here's an overview of how to enumerate over these possibilities. (This is really more of a Stack Overflow question than a question for this site, to be honest.) I suggest you use three nested loops: loop over $w$ (over the range $0\ldots N$), then loop over $x$ (over the range $0 \ldots N-w$), then loop over $y$ (over the range $0\ldots N-w-x$), then set $z=N-w-x-y$. In other words:

   for w=0,1,2,...,N:
       for x=0,1,2,...,N-w:
           for y=0,1,2,...,N-w-x:
               z = N-w-x-y
               append the row (w,x,y,z) to the matrix
   

   To generalize this code to enumerate all valid rows with $k$ columns, you should probably ask on Stack Overflow, as that's a coding question. But here's a tip. Think about how you'd enumerate all possible values of a $d$-digit odometer. You'd create an array $A[0\ldots d-1]$, initially all zeros, to hold the $d$ digits, and you'd increment through odometer values, one by one. How do you increment an odometer value? Start with your finger pointing to the rightmost digit. Increment that digit; except that if it increments from 9 to 10, that digit has rolled over, so change the 10 to a 0, move your finger left one place, and repeat the whole process (until nothing rolls over). In code, here's how you increment an odometer value:

   for i=d-1,d-2,...,2,1,0:
       A[i] = A[i]+1
       if A[i] == 10:
           A[i] = 0  // roll-over
       else:
           break out of the loop
   

   What does this have to do with your problem? Think of the first $k-1$ columns of each row as an odometer value. We're going to enumerate through them. Except, now the condition for when a digit rolls over is different: instead of rollover happening when that digit goes from 9 to 10, it will instead happen when the sum of that digit and all digits to its left goes from $N$ to $N+1$. Everything else remains the same. So, enumerate all possible values for the first $k-1$ columns, in this way. Then, you can fill in the $k$th column to whatever it needs to be to make sure the entire row sums to exactly $N$. If this doesn't help you, you might need to ask a separate question on Stack Overflow.

Once you work through the answers to all of these questions, you should have a solution. If you have gotten stuck, edit your question show us how far you got so far (e.g., which of these questions you've figured out how to answer), at what stage you've gotten stuck, and what you've tried at that stage.