我正在寻找一种算法，该算法可生成整数的固定长度分区的所有排列。顺序无所谓。
例如，对于n = 4和长度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)]
我对整数分区+长度小于L的分区的排列感到困惑；但那是太慢了，因为我在同一个分区中多次得到了（因为[0, 0, 1]可能的排列[0, 0, 1];-)
[0, 0, 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并移动到下一个位置。如果我们处于最后位置，请退后一步。
这是一个小蟒蛇，它就是这样做的：
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
现在，您有了一个列表列表（实际上是一个多集列表），并且生成列表中每个多集的所有排列都会为您提供解决方案。我将不去赘述，这里有一个递归算法，该算法基本上说，对于每个位置，选择多重集中的每个唯一元素，并追加从多重集中删除该元素所产生的多重集合的置换。
