python - 列表的 N 个不同排列的随机样本

Question

假设我有一个任意长度 k 的 Python 列表。现在，假设我想要一个 n 的随机样本，(其中 n <= k!)distinct 该列表的排列。我很想尝试:

import random
import itertools

k = 6
n = 10

mylist = list(range(0, k))

j = random.sample(list(itertools.permutations(mylist)), n)

for i in j:
  print(i)

但是，自然地，当 k 变得太大时，这段代码会变得非常慢。鉴于我可能正在寻找的排列数 n 与排列总数相比将相对较小，因此无需计算所有排列。然而，重要的是最终列表中的所有排列都不是重复的。

您将如何更有效地实现这一目标？请记住，mylist 可以是任何内容的列表，为了简单起见，我只是使用了 list(range(0, k))。

Answer 1

您可以生成排列，并跟踪您已经生成的排列。为了让它更通用，我做了一个生成器函数:

import random

k = 6
n = 10

mylist = list(range(0, k))

def perm_generator(seq):
    seen = set()
    length = len(seq)
    while True:
        perm = tuple(random.sample(seq, length))
        if perm not in seen:
            seen.add(perm)
            yield perm

rand_perms = perm_generator(mylist)

j = [next(rand_perms) for _ in range(n)]

for i in j:
    print(i)