Python:生成长度为N的所有唯一排序列表

Question

我想详尽地分析用于排序小数组的子程序,并且需要一种方法来生成特定长度的所有唯一排序的数组.在Python中,这将是具有非负整数作为元素的列表,并且最好在可能时使用最小整数.例如,N = 3:

[[0,0,0],
[0,0,1],
[0,1,0],
[0,1,1],
[0,1,2],
[0,2,1],
[1,0,0],
[1,0,1],
[1,0,2],
[1,1,0],
[1,2,0],
[2,0,1],
[2,1,0]]

[1,1,1]并[2,2,0]没有在上面的列表中属于,因为[0,0,0]并[1,1,0]分别具有相同的相对顺序,同时使用较小的整数.

Answer 1

[k_1, ..., k_n]这是 (a) 查找列表使得每个列表k_i等于k_(i-1)或k_(i-1)+1，以及 (b) 查找这些列表的唯一排列的组合。

第一个可以使用递归函数来完成：

def combinations(n, k=0):
    if n > 1:
        yield from ([k] + res for i in (0, 1)
                              for res in combinations(n-1, k+i))
    else:
        yield [k]

对于有n元素的列表，会有2^(n-1)这样的组合：

>>> list(combinations(2))
[[0, 0], [0, 1]]
>>> list(combinations(3))
[[0, 0, 0], [0, 0, 1], [0, 1, 1], [0, 1, 2]]
>>> list(combinations(4))
[[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 2], [0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2], [0, 1, 2, 3]]

将其与itertools.permutations过滤掉重复项以获得最终结果：

import itertools
def all_combinations(n):
    return (x for combs in combinations(n)
              for x in set(itertools.permutations(combs)))

例子：

>>> list(all_combinations(3))
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
>>> sum(1 for _ in all_combinations(4))
75
>>> sum(1 for _ in all_combinations(5))
541

注意：即使对于稍大的值，生成所有 n!排列然后过滤重复项也可能非常n浪费。有一些更智能的方法可以仅生成可以用来代替的唯一排列itertools.permutations，请参见例如此处或此处。