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

Question

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

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

Na\xc3\xafve 实现

\n\n

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

\n\n

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

\n\n

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

\n\n

关键思想是：

\n\n

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

\n\n

这个 na\xc3\xafve 版本不会直接受到函数的阶乘复杂性O(k!)的影响，该函数在采样之前itertools.permutations会生成所有排列。k!

\n\n

关于复杂性

\n\n

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

\n\n

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

\n\n

局限性

\n\n

我们来封装一下@Tomothy32写的函数：

\n\n

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

\n\n

例如，此调用适用于非常小的情况k<7：

\n\n

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

\n\n

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

\n\n

永远往好的一面看...

\n\n

另一方面，当 时，该方法似乎可以在合理的时间内生成合理数量的排列元组N<<<k!。例如，可以在不到一秒的时间内绘制多个N=5000长度的元组。k10 < k < 1000

\n\n

\n

\n\n

当k和N保持较小且N<<<k!时，算法似乎具有复杂性：

\n\n

\n
• 常数与k；
\n
• 线性与N.
\n

\n\n

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

\n