Uniquely generate all permutations of three digits that sum to a particular value? 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.
 A: 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)]
A: 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.  
A: 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.
A: 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;
}

A: 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.
A: 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!
A: 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

A: 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$.
A: 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;
  }

A: 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]);
}

A: This maybe overkill, but here is my generalized algorithm:
http://nbviewer.ipython.org/gist/denfromufa/61b3ed4e902fd9d11d6a
