Uniquely generate all permutations of three digits that sum to a particular value?

Question

I'm looking for a way of generating all permutations of three digits (actually xyz) that sum to the same value.

For example:

n = 1:

0 0 0

n = 2:

0 0 1
0 1 0
1 0 0

n = 3:

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

n = 4:

1 1 2
...

Ideally I need a way of mapping indices to the three digits in a unique way such that I can take an index up to the associated triangle number n * (n + 1) / 2 and find the same three indices every time.

Can anyone point me in the right direction? It's quite some time since I've worked with sequences and I'm a little rusty.

Answer 1

Your question is how to list the ways to multichoose the positions of $n$ balls in 3 boxes. You could more generally list the ways to multichoose the positions of $k$ balls in $n$ boxes.

The clearest theoretical answer is given by the "stars and bars" construction. Multiset coefficients and the stars and bars construction are explained very nicely in Wikipedia. Here is a Python code inspired by the stars-and-bars bijection between multiset choices and ordinary subset choices.

def multichoose(n,k):
    if k < 0 or n < 0: return "Error"
    if not k: return [[0]*n]
    if not n: return []
    if n == 1: return [[k]]
    return [[0]+val for val in multichoose(n-1,k)] + \
        [[val[0]+1]+val[1:] for val in multichoose(n,k-1)]

Evaluate multichoose(3,4) and see what you get!

Answer 2

Since the problem requires 3 numbers only, we can easily use iteration to solve the problem, instead of recursion. Greg Kuperberg's answer is probably better, if we are finding n numbers summing to N. Here is the python code for the function permutation:

def per(n):
       a = []
       for i in range(n):
           for j in range(n-i):
               a.append((i, j, n-i-j-1))
       return a

per(3) = [(0, 0, 2), (0, 1, 1), (0, 2, 0), (1, 0, 1), (1, 1, 0), (2, 0, 0)]

per(4)=[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

Answer 3

You can do it in one line in Maple:

choose := n -> map2(map, `-`, combinat[composition](n+3,3), 1);

The $n+3$ is because compositions are 1-based, not 0-based. multichoose would just be

multichoose := (n,k) -> map2(map, `-`, combinat[composition](n+k,k), 1);

For much more sophisticated manipulations of these, look at the 'combstruct' package, which gives you ways to count, exhaustively and randomly generate these (and anything else you can specify as a combinatorial structure, roughly corresponding to Species). The algorithms implemented in combstruct are, AFAIK, 'optimal' in their running time. The fun part about that package is that it's actually written as a generator -- you write a specification of a combinatorial structure, and it generates the code that does exhaustive and random generation.

Answer 4

The answer is detailed (along with MATLAB code) at

http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/

and successive posts. Use the MATLAB function "lookup" to produce the graded lex order.

Answer 5

I had the same problem, but for any n multichoose k. I also needed a non-recursive algorithm to resolve it as my performance requirements are strict.

I couldn't find a non-recursive solution anywhere on the web, so I implemented one in C++ (for generic vectors) and C. See: http://github.com/ekg/multichoose, specifically multichoose.h:

template <class T>
std::vector< std::vector<T> > multichoose(int k, std::vector<T>& objects) {
    std::vector< std::vector<T> > choices;
    int j,j_1,q,r;
    r = objects.size() - 1;
    std::vector<T*> a, b; // combination indexes
    for (int i=0;i<k;i++) {
        a.push_back(&objects[0]); b.push_back(&objects[r]);
    }
    j=k;
    while(1){
        std::vector<T> multiset;
        for(int i=0;i<k;i++)
            multiset.push_back(*a[i]);
        choices.push_back(multiset);
        j=k;
        do { j--; } while(a[j]==b[j]);
        if (j<0) break;
        j_1=j;
        while(j_1<=k-1){
            a[j_1]=a[j_1]+1;
            q=j_1;
            while(q<k-1) {
                a[q+1]=a[q];
                q++;
            }
            q++;
            j_1=q;
        }
    }
    return choices;
}

Answer 6

This is a Python implementation of the above non-recursive (and lexicographically ordered!) solution. The C++ implementation generates the multisets by manipulating pointers while this one uses an array of indexes in objects. Additionally, this implementation returns a generator.

def multichoose(k, objects):
    """n multichoose k multisets from the list of objects.  n is the size of
    the objects."""
    j,j_1,q = k,k,k  # init here for scoping
    r = len(objects) - 1
    a = [0 for i in range(k)] # initial multiset indexes
    while True:
        yield [objects[a[i]] for i in range(0,k)]  # emit result
        j = k - 1
        while j >= 0 and a[j] == r: j -= 1
        if j < 0: break  # check for end condition
        j_1 = j
        while j_1 <= k - 1:
            a[j_1] = a[j_1] + 1 # increment
            q = j_1
            while q < k - 1:
                a[q+1] = a[q] # shift left
                q += 1
            q += 1
            j_1 = q

The algorithm works by encoding the changes between successive items in the set of results to n multichoose k as index increments and array shifts. I think that this method is intuitive in the sense that it approximates how we (or at least I) write down these combinations by hand, by following a series of minimal changes between multiset combinations to progress through the result space.

If you want to understand its operation I suggest instrumenting the inner while loop with some print a statements before and after the increment and shift left operations. This should make what's happening a bit clearer. You could probably optimize this to run in slightly fewer ops if the lexicographic ordering weren't important. I haven't tried as I find that aspect very useful.

I've included this implementation in the git repo I mentioned in my other answer.

Thanks go to Tad Takaoka for his work in generating multiset combinations and permutations.

Answer 7

This is essentially ordering the lattice points intersected by a plane in three space in the all-positive-or-zero octant where the sum of the $x,y,z$-coordinates is $n$.

(I may be mistaken but your example for n=1,2,3 show the values for n=0,1,2, and your example for n=4 does show the answer for 4, so I think you're off by one for part of your example. And you use the word permutation, but your description of the problem is more aptly states as combination of three integers.)

This is essentially a simple geometric problem in 3-space over the integers, unless I am misunderstanding your question.

If you look at it geometrically, you are looking at the points on the lattice $\mathbb {Z}^3$ and finding the points on the plane $x+y+z=n$ in the all positive-or-zero-octant $x\ge0, y\ge0, z\ge0$. You can then order the lattice points which satisfy these constraints ordinally in whatever order you prefer, say numerically with $x$-coordinate taking precedence over $y$ taking precedence over $z$.

In this case, it is easy to read off the coordinates of the triangle in the all-positive octant of 3-space.

for x = 0 to n
for y = 0 to n-x
z = n-x-y
print x,y,z
next y
next x

Answer 8

This really is the same as finding the plane $x+y+z=n$ in 3-space $\mathbb{R}^3$ and finding the intersection of this plane with the lattice points in $\mathbb{Z}^3$.

Octave code (also matlab code) which returns answers in lexicographical order:

for x=0:n
for y=0:(n-x) % y must be less than (n-x+1)
z=(n-x-y); % semicolor suppresses printing
disp([x y z])
end y,x

Don't make it more complicated than it has to be. Also similar answer below. For every point on the 2-d lattice, $\mathbb{Z}^2$, calculate the $z=n-x-y$ value, and it's a valid answer for $0 \le z \le n$, $x \ge 0$, $y \ge 0$.

Answer 9

Visualizing this problem, as unique ways to hand out ninja stars to ninjas. This also shows how each larger solution is made up of its neighboring, more simple solutions.

alt text http://www.freeimagehosting.net/uploads/58531735d3.png

Here is how to implement it in php: (might help you understand it too)

function multichoose($k,$n)
{
 if ($k < 0 || $n < 0) return false;
 if ($k==0) return array(array_fill(0,$n,0));
 if ($n==0) return array();
 if ($n==1) return array(array($k));
 foreach(multichoose($k,$n-1) as $in){ //Gets from a smaller solution -above as (blue)
  array_unshift($in,0);  //This prepends the array with a 0 -above as (grey)
  $out[]=$in;
 }
 foreach(multichoose($k-1,$n) as $in){ //Gets the next part from a smaller solution too. -above as (red and orange)
  $in[0]++; //Increments the first row by one -above as (orange)
  $out[]=$in;
 }
 return $out;
}

print_r(multichoose(3,4)); //How many ways to give three ninja stars to four ninjas?

Not optimal code: Its more understandable that way.

Our output:

(0,0,0,3)
(0,0,1,2)
(0,0,2,1)
(0,0,3,0)
(0,1,0,2)
(0,1,1,1)
(0,1,2,0)
(0,2,0,1)
(0,2,1,0)
(0,3,0,0)
(1,0,0,2)
(1,0,1,1)
(1,0,2,0)
(1,1,0,1)
(1,1,1,0)
(1,2,0,0)
(2,0,0,1)
(2,0,1,0)
(2,1,0,0)
(3,0,0,0)

Fun use to note: Upc relies upon this exact problem in barcodes. The sum of the whitespace and blackspace for each number is always 7, but is distributed in different ways.

//Digit   L Pattern  R Pattern  L\R Pattern (Number of times a bit is repeated)
    0   0001101    1110010    2100
    1   0011001    1100110    1110
    2   0010011    1101100    1011
    3   0111101    1000010    0300
    4   0100011    1011100    0021
    5   0110001    1001110    0120
    6   0101111    1010000    0003
    7   0111011    1000100    0201
    8   0110111    1001000    0102
    9   0001011    1110100    2001

Note only 10 of the 20 combinations are used, which means the code can be read upside-down just fine. All 20 can be used however, and are in EAN13, with a bit more complexity.

http://en.wikipedia.org/wiki/EAN-13

http://en.wikipedia.org/wiki/Universal_Product_Code

http://www.freeimagehosting.net/uploads/58531735d3.png

Answer 10

In javascript for anyone who needs it:

  var multichoose: function(n, k) {
    if(k < 0 || n < 0)
      return;

    if(k == 0) {
      var arr = []
      for(var i = 0; i < n; i++) { arr.push(0); }
      return [arr];
    }
    if(n == 0) {
      return [];
    }

    if(n == 1) {
      return [[k]];
    }

    var arr = this.multichoose(n - 1, k);
    var arr2 = this.multichoose(n, k - 1);
    var out = [];

    for(var i = 0; i < arr.length; i++) {
      arr[i].unshift(0);
      out.push(arr[i]);
    }

    for(var i = 0; i < arr2.length; i++) {
      arr2[i][0]++;
      out.push(arr2[i]);
    }

    return out;
  }

Answer 11

And again for Java if someone needs it:

    public static int[][] multichoose(int k, int n) {

    if (k < 0 || n < 0) return null;
    if (k == 0) return new int[1][n];
    if (n == 0) return new int[0][0];

    if (n == 1) {
        int[][] result = new int[1][1];
        result[0][0] = k;
        return result;
    }

    int[][] arr = multichoose(k, n - 1);
    int[][] arr2 = multichoose(k - 1, n);
    List<int[]> out = new ArrayList<>();

    for (int i = 0; i < arr.length; i++) {
        int[] trans = new int[arr[i].length + 1];
        trans[0] = 0;
        System.arraycopy(arr[i], 0, trans, 1, arr[i].length);
        out.add(trans);
    }

    for (int i = 0; i < arr2.length; i++) {
        arr2[i][0]++;
        out.add(arr2[i]);
    }

    return out.toArray(new int[0][0]);
}

Answer 12

This maybe overkill, but here is my generalized algorithm:

http://nbviewer.ipython.org/gist/denfromufa/61b3ed4e902fd9d11d6a