7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The 'generating-functions' tag is quite unrelated. $\endgroup$ Dec 21, 2009 at 16:06
  • $\begingroup$ I removed the generating-functions tag. $\endgroup$ Dec 21, 2009 at 16:11
  • $\begingroup$ For enumeration problems of this kind it is often of interest to have the consecutive items in the list (including between the last and first) be "near each other." This type enumeration is called a "Gray code," for Frank Gray who carried out an enumeration of this kind for the binary sequences of length n. For the binary sequences the idea was to have consecutive sequences have Hamming distance 1 between them. So the Gray code for this case is a Hamiltonian circuit on the n-cube. $\endgroup$ Dec 21, 2009 at 18:39
  • 4
    $\begingroup$ Because @Mariano says this has nothing to do with generating functions I feel duty bound to point out that Mathematica will compute what you want using a generating function if you ask it for the coefficient of $t^k$ in $\prod_{i=1}^n 1/(1-tx_i^n)$. Each term corresponds to one of the sums you want, and you extract the $i$th digit of the sum by reading off the power of $x_i$ in that term. :-) $\endgroup$
    – Dan Piponi
    Apr 28, 2010 at 0:56

12 Answers 12

10
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
2
$\begingroup$

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;
}
$\endgroup$
3
  • $\begingroup$ Can you post pseudocode? $\endgroup$ Apr 29, 2010 at 20:02
  • $\begingroup$ I'll do one in Python. Close enough? :) $\endgroup$ Apr 29, 2010 at 21:16
  • $\begingroup$ Guess so. I'm dying to see how to do this nonrecursively. I've used recursive code for this for a decade, though I never had a need to make it go fast. $\endgroup$ Apr 29, 2010 at 22:15
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I think I've fallen slightly off-topic :) $\endgroup$ May 1, 2010 at 13:35
  • $\begingroup$ Erik--Thanks for posting the Python, this algorithm sounds really cool and the Python should make dissecting and reproducing it a whole lot easier. FYI, if you use graded lex ordering a lot you may be interested in the fast indexing techniques provided in the series of posts referenced in my old answer on this page. (I can provide the MATLAB and maybe some Java code under GPL or Apache.) $\endgroup$ May 1, 2010 at 15:46
  • $\begingroup$ Steve-- Glad it's useful. Apologies for the somewhat cryptic variable naming of the index variables. I adapted one of Prof. Takaoka's implementations to this application, and I kept the naming. $\endgroup$ May 4, 2010 at 21:19
1
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Very nice. Simple answer that produces a natural ordering over the triangle on $\mathbb{Z}^2$. Similar (?) to one below. :) . $\endgroup$ Sep 11, 2010 at 4:26
  • $\begingroup$ Sorry. :), didn't see your code below. Though this code is for octave rather than for BASIC. $\endgroup$
    – user9149
    Sep 13, 2010 at 23:16
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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;
  }
$\endgroup$
0
$\begingroup$

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]);
}
$\endgroup$
-1
$\begingroup$

This maybe overkill, but here is my generalized algorithm:

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

$\endgroup$

Your Answer

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

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