在 Python 中流式传输嵌套列表（列表的列表）中元素的所有 unordered/shuffled 唯一排列？

Question

我有如下两级嵌套列表。

[[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]

我想生成此嵌套列表的所有 8 个 唯一排列，但我的应用程序 绝对需要输出是（伪）随机和无序的。 通常，排列策略会按顺序生成排列，但我希望能够乱序生成所有排列。

此外，这 MUST 可以通过一些生成器来完成，因为嵌套列表可以很长，并且唯一排列的数量可以组合爆炸式增长。

例如，上面的列表需要以下输出。

(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)

...与以下内容相反，它由 itertools.product(*some_list) 生成：

(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(0, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 3, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 11, 12)
(1, 2, 4, 5, 6, 7, 8, 9, 10, 12)

即使某些解决方案完全符合 itertools.product 的要求，但会产生乱序的排列，这对我有很大帮助。感谢任何帮助。

以下代码说明了我现有的方法。

def perm_attempt():
    meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
    print meta_seq
    iter_count = np.prod([len(set(x)) for x in meta_seq])
    print iter_count
    print
    set_l = set()
    for _ in xrange(iter_count*10):
        l = [np.random.choice(x) for x in meta_seq]
        # print l
        set_l.add(tuple(l))
    print
    print len(set_l)
    print
    # for s in set_l:
    #     print s

Answer 1

您可以尝试迭代以下生成器：

def random_perm(l):
    while True:
        yield [random.choice(sublist) for sublist in l]

示例用法：

l = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
g = random_perm(l)
for _ in range(10):
    print(next(g))

输出：

[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 3, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 11, 12]
[1, 2, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 2, 4, 5, 6, 7, 8, 9, 10, 12]

但是，正如其他人在评论中指出的那样，除非您以某种方式将收益结果缓存在内存中，否则您无法真正保证不会重复。您也不能保证在任何 8 个连续迭代中获得所有 8 个唯一迭代。

Answer 2

如果内存不会有问题，您可以尝试以下方法：

permList = itertools.product(*list_of_lists)
randomPermList = numpy.random.permutation(list(permList))

这是唯一且随机的，但不会是迭代。

Answer 3

比您当前的解决方案更简洁：

meta_seq = [[0, 1], [2], [3, 4], [5, 5], [6], [7], [8], [9], [10, 11], [12]]
print meta_seq
iter_count = np.prod([len(set(x)) for x in meta_seq])
print iter_count
print
set_l = set()
for _ in xrange(iter_count*100):
    choices = tuple([np.random.choice(sub_seq) for sub_seq in meta_seq])
    if not choices in set_l:
        set_l.add(choices)
        print choices
print
print len(set_l)
print

在 Python 中流式传输嵌套列表（列表的列表）中元素的所有 unordered/shuffled 唯一排列？

Stream all unordered/shuffled unique permutation of elements in a nested list (list of list) in Python?

python

algorithm

graph

combinatorics

itertools