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

Question

假设我有一个 Python 任意长度的列表 k。现在，假设我想要 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 与排列总数相比将相对较小，因此无需计算所有排列。然而，重要的是最终列表中 none 的排列是重复的。

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

Answer 1

天真的实现

下面是我所做的幼稚实现（@Tomothy32 很好地实现了，使用生成器的纯 PSL）：

import numpy as np

mylist = np.array(mylist)
perms = set()
for i in range(n):                          # (1) Draw N samples from permutations Universe U (#U = k!)
    while True:                             # (2) Endless loop
        perm = np.random.permutation(k)     # (3) Generate a random permutation form U
        key = tuple(perm)
        if key not in perms:                # (4) Check if permutation already has been drawn (hash table)
            perms.update(key)               # (5) Insert into set
            break                           # (6) Break the endless loop
    print(i, mylist[perm])

它依赖于 numpy.random.permutation 随机排列一个序列。

关键思想是：

生成新的随机排列（索引随机排列）；
检查排列是否已经存在并存储它（作为 int 的 tuple 因为它必须散列）以防止重复；
然后使用索引置换对原始列表进行置换。

这个朴素的版本不会直接受到 itertools.permutations 函数的阶乘复杂度 O(k!) 的影响，它会在从中采样之前生成所有 k! 排列。

关于复杂性

算法设计和复杂性有些有趣的地方...

如果我们想确保循环可以结束，我们必须执行 N <= k!，但不能保证。此外，评估复杂性需要知道在找到并打破新的随机元组之前无限循环实际循环了多少次。

限制

把@Tomothy32写的函数封装一下：

import math
def get_perms(seq, N=10):
    rand_perms = perm_generator(mylist)
    return [next(rand_perms) for _ in range(N)]

例如，此调用适用于非常小的 k<7:

get_perms(list(range(k)), math.factorial(k))

但是当 k 增长时会在 O(k!) 复杂性（时间和内存）之前失败，因为它归结为在找到所有其他 k!-1 键时随机找到一个唯一的缺失键.

永远往好的方面看...

另一方面，当 N<<<k! 时，该方法似乎可以在合理的时间内生成合理数量的置换元组。例如，可以在不到一秒的时间内绘制超过 N=5000 个长度为 k 的元组，其中 10 < k < 1000。

当k和N保持较小和N<<<k!时，算法似乎有一个复杂度：

常量与 k;
线性与 N.

这在某种程度上是有价值的。

Answer 2

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

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)

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

Random Sample of N Distinct Permutations of a List

python

random

permutation

discrete-mathematics

python-3.x

天真的实现

关于复杂性

限制

永远往好的方面看...