1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't understand the requirements. Can all the rows be the same? Can all the values in a single row be the same? Can I just put $N,0,0,0$ in every row? Can you edit the question to clarify these points as well as addressing Dukeling's questions? $\endgroup$ – D.W. Aug 1 '13 at 22:40
  • $\begingroup$ Moreover, can you tell us in what context you ran into this problem (e.g., what is the motivation/application?), and what you've tried so far and where you've gotten stuck? On this site you are expected to make a serious effort on your own first, so it helps to include evidence of that in your question -- and showing us what you've tried so far in your question may help us give you better answers. $\endgroup$ – D.W. Aug 2 '13 at 1:19
  • $\begingroup$ @ D.W.: the rows should be distinct. The question arose whilst trying to write a program that found optimal rewards for a 2-armed bandit. I wasn't really sure where to start, and was running into issues with where to start/finish for loops. $\endgroup$ – lokodiz Aug 2 '13 at 9:33
  • 2
    $\begingroup$ So you want all permutations of all partitions of $N$ -- why? $\endgroup$ – Raphael Aug 11 '13 at 12:12
  • 1
    $\begingroup$ Generating all partitions is covered by Knuth's TAoCP volume 4, section 7.2.1.4 (with pseudocode). $\endgroup$ – András Salamon Aug 12 '13 at 8:29
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I'm trying to convert this into R, and I see how it works on paper, but I'm not understanding some things. At the moment, my code only prints the last row (0,0,0,2). How is it that your code isn't overwriting the static (is this the same thing as 'global'?) variable 'array' for each separate recursion? $\endgroup$ – lokodiz Aug 5 '13 at 9:16
  • $\begingroup$ It's only static because it's easier to make it that, it doesn't have to be. But yes, I believe array would be a global variable in R. It only creates the array once here - array = new int[2*N];, because only the first function call will have pos == 0, every following call with have a greater pos. It does overwrite the values in array from the previous recursive steps, but it prints the array as it goes. You'll probably either have to do the same, or add them to a list which you return or a global list. $\endgroup$ – Dukeling Aug 5 '13 at 9:31
  • $\begingroup$ Hmm, I'll edit my original post with my attempted version in R. Would you be able to see what's going wrong? I'm not sure if the for loops / if statements are correct. (For what it's worth, the number of columns need not be 2N. In fact, in my modified program, the number of columns can be specified by the user.) $\endgroup$ – lokodiz Aug 5 '13 at 9:40
  • $\begingroup$ You shouldn't be returning in the for-loop, and I don't think you can return more than one thing, you need to add the arrays to a list or print them. I managed to put this hacky version together. For some reason, every time it went down 1 step in the recursive function, it resets the array values. I couldn't figure that out (I don't really know R), so I passed the array around. $\endgroup$ – Dukeling Aug 5 '13 at 10:37
  • $\begingroup$ Thanks a lot! Working off your program, I made this inelegant program: ideone.com/p3SMLY . I really need to learn how to use global variables in R... $\endgroup$ – lokodiz Aug 5 '13 at 13:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In regards to your third point, is it not (N+1)(N+2)(N+3)/6 (the value I [seemingly randomly] specified in my original question)? Thanks for the general advice, though. I'll try to work on this and get back to you. $\endgroup$ – lokodiz Aug 2 '13 at 11:42
  • $\begingroup$ For 1, the only requirements are w+x+y+z = N and (w,x,y,z) != (w',x',y',z') for any other row in the matrix. For 2, yes, provided that we don't have equality between the rows. For 5, I really don't know what the best way to attack this would be. $\endgroup$ – lokodiz Aug 2 '13 at 14:43
  • $\begingroup$ @SimonC, OK, I've updated my answer to show how to deal with #5. I hope that helps. $\endgroup$ – D.W. Aug 2 '13 at 19:02
  • $\begingroup$ @ D.W. That's really useful, thanks. If I were wanting to generalise this to k columns (rather than just k=4) would this strategy still be applicable (since the number of for loops would vary with k)? $\endgroup$ – lokodiz Aug 5 '13 at 9:24
  • $\begingroup$ OK, @SimonC, I've edited my question to answer your latest additional question. But in the future: programming questions (questions about how to express something in code) should go on Stack Overflow, not here. $\endgroup$ – D.W. Aug 5 '13 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.