算法生成固定长度的整数分区的所有独特的排列？ [英] Algorithm to generate all unique permutations of fixed-length integer partitions?

问题描述

我搜索的算法生成整数的固定长度分区的所有排列。顺序并不重要。

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

例如，对于n = 4和长度L = 3：

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

我bumbled约整数分区+排列的分区，它的长度是不是L-较小;但太慢了，因为我得到了相同的分区多次（因为 [0，0，1] 可能的置换 [0,0 ，1] ; - ）

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

任何帮助AP preciated，不，这不是功课 - 个人兴趣： - ）

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

推荐答案

好。首先，忘了排列，只是产生的长度L分区（所建议的@Svein Bringsli）。注意，对于每个分区，则可能对元件，例如>的排序。现在只是算，维护您的订购。对于n = 4，k = 3的

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)

那么，如何实现这一点？它看起来像：同时减去1位置i并将其添加到下一个位置保持我们的订单，减去1从位置i，加1到位置i + 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.

这篇关于算法生成固定长度的整数分区的所有独特的排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！