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

这是 (a) 查找列表 [k_1, ..., k_n] 的组合，使得每个 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，参见例如here或 here .