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

好的。首先，忘记排列，只生成长度为 L 的分区（如 @Svein Bringsli 所建议）。请注意，对于每个分区，您可以对元素进行排序，例如 >。现在只需“计数”即可维持您的顺序。对于 n = 4，k = 3：

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

那么，如何实施呢？看起来像：在位置 i 减 1 并将其添加到下一个位置保持我们的顺序的同时，从位置 i 减 1，在位置 i + 1 加 1，然后移动到下一个位置。如果我们处于最后位置，请退后一步。

这是一个小Python，它就是这样做的：

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

现在您有了一个列表列表（实际上是一个多重集列表），生成列表中每个多重集的所有排列即可为您提供解决方案。我不会详细讨论这个，有一个递归算法，它基本上说，对于每个位置，选择多重集中的每个唯一元素，并附加从多重集中删除该元素所产生的多重集的排列。