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] 分别具有相同的相对顺序。

- ZyTelevan

---

我会提到 itertools.product - 但是我不理解最后一句话，为什么一些通常使用的元素不属于你所需的列表... - SpghttCd

从排序的角度来看，如果我只能比较一个项目是否小于、大于或等于另一个项目，那么列表[2,2,0]等同于[1,1,0]，因此我不需要测试相同的排序两次。 - ZyTelevan

根据你最后一句话的逻辑，[0,0,1]和[1,1,0]都应该属于吗？ - Him

也许你可以从 itertools.combinations_with_replacement(range(3),3) 开始，然后进行过滤，但毫无疑问会有更好的方法。 - Chris_Rands

@DanielMesejo 在 [0,2,1] 中，第一项小于第二项和第三项；第二项大于第一项和第三项；第三项大于第一项但小于第二项。在 [0,1,0] 中，第一项小于第二项且等于第三项；第二项大于第一项和第三项；第三项等于第一项且小于第二项。 - ZyTelevan

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，例如请参见 这里 或 这里。

- tobias_k

Answer 2

你可以遍历range的笛卡尔积，对于每个元素，使用相对顺序作为键，并将(相对顺序，元组)对存储在字典中，最后返回排序后的结果：

def uniquely_ordered_list(n=3):
    def key(o):
        relative = ['equal'] + ['less' if a < b else ('greater' if a > b else 'equal') for a, b in product(o, repeat=2)]
        return tuple(relative)

    found = {}
    for ordering in product(range(n), repeat=n):
        if key(ordering) not in found:
            found[key(ordering)] = ordering

    return sorted(found.values())

输出

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

更新

如@tobias_k所建议，您可以使用以下函数作为密钥:

def key(o):
    sign = lambda x: x / abs(x) if x else x
    return tuple([0] + [sign(a - b) for a, b in product(o, repeat=2)])

- Dani Mesejo

---

这与我的方法产生了不同的结果，例如对于n=4，我的结果是75，而你的结果是51。特别地，你似乎根本没有考虑组合(0,1,2,3)，并且似乎认为(0,2,2,1)等同于(0,1,1,0)，尽管它们在排序后是不同的（而OP的问题是关于排序测试用例的）。（并不是说这一定是错误的，只是想指出差异。） - tobias_k

@tobias_k 已修复！只是一个小错误，range(3)应该是range(n)，使用range(n)后，生成的结果与你的一样为75。 - Dani Mesejo

说实话，我还在努力理解这个到底是如何工作的，但它似乎是有效的。当然，复杂度是O(可怕)，但我的也是。也许你可以简化一下key，改成return tuple(sign(a - b) for a, b in product(o, repeat=2))，其中sign = lambda x: x / abs(x) if x else x。 - tobias_k

Answer 3

这里有另一个解决方案：

import numpy as np
from itertools import product, combinations

def rord(lst):
    ''' Maps the relative order of a list 'lst' to a unique string of 0, 1, and 2.

    Relative order is computed by converting the list 'sgns' of all 
    the values sgn(lst[i]-lst[j])+1, for i<j, i,j = 0,..., n-1,
    to a string.

    E.g. the lists [0, 0, 1], [0, 0, 2] and [1, 1, 2] have the same rord = '100'
    because lst[0] = lst[1], lst[0] < lst[1], lst[1] < lst[2] for all
    of them, so sgns = [1, 0, 0]
    '''
    sgns = np.sign([tup[0]-tup[1] for tup in combinations(lst, 2)]) + 1
    return ''.join(str(e) for e in sgns)  # return sgns.tostring() is faster


def uniq_rord_lst(n):
    '''Returns n-length sequences of integers 0,... n-1, with unique relative
    order. E.g. for n=2 returns [(0, 0), (0, 1), (1, 0)].
    '''
    seen_ro = set()
    result = []
    for comb in product(range(n), repeat=n):
        ro = rord(comb)
        if ro not in seen_ro:
            seen_ro.add(ro)
            result.append(comb)
    return result

例子：

>>> uniq_rord_lst(2)
[(0, 0), (0, 1), (1, 0)]

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

更新：更快的一个

def uniq_rord_lst(n):
    seen_ro = set()
    result = []
    for comb in product(range(n), repeat=n):
        ro = tuple(sorted(comb).index(x) for x in comb)
        if ro not in seen_ro:
            seen_ro.add(ro)
            result.append(comb)           
    return result

- Andreas K.