Algorithm to generate all unique permutations of fixed-length integer partitions?

Question

I'm searching for an algorithm that generates all permutations of fixed-length partitions of an integer. Order does not matter.

For example, for n=4 and length L=3:

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

I bumbled about with integer partitions + permutations for partitions whose length is lesser than L; but that was too slow because I got the same partition multiple times (because [0, 0, 1] may be a permutation of [0, 0, 1] ;-)

Any help appreciated, and no, this isn't homework -- personal interest :-)

Answer 1

Okay. First, forget about the permutations and just generate the partitions of length L (as suggested by @Svein Bringsli). Note that for each partition, you may impose an ordering on the elements, such as >. Now just "count," maintaining your ordering. For n = 4, k = 3:

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

So, how to implement this? It looks like: while subtracting 1 from position i and adding it to the next position maintains our order, subtract 1 from position i, add 1 to position i + 1, and move to the next position. If we're in the last position, step back.

Here's a little python which does just that:

def partition_helper(l, i, result):
    if i == len(l) - 1:
        return 
    while l[i] - 1 >= l[i + 1] + 1:
        l[i]        -= 1
        l[i + 1]    += 1
        result.append(list(l))
        partition_helper(l, i + 1, result)

def partition(n, k):
    l = [n] + [0] * (k - 1)
    result = [list(l)]
    partition_helper(l, 0, result)
    return result

Now you have a list of lists (really a list of multisets), and generating all permutations of each multiset of the list gives you your solution. I won't go into that, there's a recursive algorithm which basically says, for each position, choose each unique element in the multiset and append the permutations of the multiset resulting from removing that element from the multiset.

Answer 2

Given that you ask this out of interest, you would probably be interested an authorative answer! It can be found in "7.2.1.2 - Generating all permutations" of Knuth's The Art of Computer Programming (subvolume 4A).

Also, 3 concrete algorithms can be found here.