如何从列表中随机抽样并保持顺序？
我有一个已经排好序的列表，比如说：（其实这不仅仅是数字，而是一些经过复杂且耗时算法排序的对象）
mylist = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,9 , 10 ]
有没有什么Python函数可以让我获取N个项目，同时保持它们的顺序呢？
举个例子：
randomList = getRandom(mylist,4)
# randomList = [ 3 , 6 ,7 , 9 ]
randomList = getRandom(mylist,4)
# randomList = [ 1 , 2 , 4 , 8 ]
等等...
5 个回答
也许你可以先生成一些索引的样本，然后从你的列表中收集对应的项目。
randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]
简单易懂的 O(#picks*log(#picks)) 方法
先随机抽取一些索引，不放回，然后对这些索引进行排序，再从原始数据中取出对应的值。
indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]
random.sample(seq, K) 这个函数会从 seq 中随机选出 K 个元素，而且是同时选的，不会重复。当我们用 range 来做这个时，每次抽样的时间复杂度是 O(1)，因为在 Python 中，range 对象是稀疏的，并不会真正生成一个完整的列表（具体来说，CPython 实现中会调用 len(seq) 和后面的 seq[i]，这些都是虚拟的，所以是 O(1)）。然后你就可以按顺序查找这些随机索引了。
如果你有一个迭代器（比如生成器表达式），你可以先把它转换成列表，然后再用上面的方法。如果你的迭代器长度不确定，可以使用下一节提到的技术，虽然性能较差，但可能会让你觉得有趣（比如在一些不支持索引的函数式语言中处理小的有限列表，或者处理超出内存和磁盘大小的巨大数据流）：
（还有一个用户 tegan 在评论中提到的有用提示：如果你用的是 Python2，记得用 xrange，像往常一样。否则，你的算法复杂度会是 O(N)，而不是 O(#picks)。）
慢速/可流式处理的 O(arrayLen)-时间，O(1)-辅助空间方法，适用于不可索引的序列
你还可以用一个数学技巧，逐个从左到右遍历 myList，以动态变化的概率 (N-numbersPicked)/(total-numbersVisited) 来选择数字。这种方法的时间复杂度是 O(N)，因为它只访问每个元素一次（比排序快，排序是 O(N log(N))，但比直接索引 K 个选择要慢，后者在排序后是 O(K log(K))）。
from __future__ import division
def orderedSampleWithoutReplacement(seq, k):
if not 0<=k<=len(seq):
raise ValueError('Required that 0 <= sample_size <= population_size')
numbersPicked = 0
for i,number in enumerate(seq):
prob = (k-numbersPicked)/(len(seq)-i)
if random.random() < prob:
yield number
numbersPicked += 1
证明：考虑从大小为 len(seq) 的总体 seq 中均匀抽取一个大小为 k 的子集，我们可以在任意点 i 进行划分，分为 '左'（0,1,...,i-1）和 '右'（i,i+1,...,len(seq)）。假设我们从左边的已知子集中抽取了 numbersPicked，那么剩下的必须来自右边的未知子集，虽然参数不同。特别地，seq[i] 包含一个被选中元素的概率是 #remainingToChoose/#remainingToChooseFrom，或者 (k-numbersPicked)/(len(seq)-i)，所以我们模拟这个过程并递归处理结果。（这个过程会终止，因为如果 #remainingToChoose == #remainingToChooseFrom，那么所有剩余的概率都是 1。）这类似于一个动态生成的概率树。基本上，你可以通过依赖之前的选择来模拟均匀的概率分布（随着概率树的增长，你选择当前分支的概率，使其在后验上与之前的叶子相同，即基于之前的选择；这会有效，因为这个概率是均匀的，正好是 N/k）。
（你可以查看这篇文章的编辑历史，找到之前为了应对一些负面评价而需要的详细模拟“证明”。）
下面是另一种编码方式，使用了更具语义的变量名。
from __future__ import division
import random
def orderedSampleWithoutReplacement(seq, sampleSize):
totalElems = len(seq)
if not 0<=sampleSize<=totalElems:
raise ValueError('Required that 0 <= sample_size <= population_size')
picksRemaining = sampleSize
for elemsSeen,element in enumerate(seq):
elemsRemaining = totalElems - elemsSeen
prob = picksRemaining/elemsRemaining
if random.random() < prob:
yield element
picksRemaining -= 1
from collections import Counter
Counter(
tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
for _ in range(10**5)
)
编辑：Timothy Shields 提到 水库抽样，这有点像这种方法（但从候选选项开始，并随机替换），在 len(seq) 不确定时非常有用（比如使用生成器表达式）。特别是被称为“算法 R”的方法是 O(N) 和 O(1) 辅助空间，如果就地进行；它涉及先取前 K 个元素，然后慢慢替换它们（也给出了归纳证明的提示）。在维基百科页面上还有水库抽样的有用变体。这个方法的思路是，你预先填充一个候选返回值的列表（假设它可以放入内存或磁盘中），然后在遍历列表时以概率方式替换它们（这个列表可能比你的内存或磁盘大得多）。
最优的 O(#picks * (1+log(N/#picks)))-时间，O(1)-辅助空间方法，适用于可索引的序列
一个值得注意的算法在水库抽样的文章中（按 Ctrl-F 查找 算法 L 部分 “一个最优算法”）：这是一个竞争因子最优的算法，和原始解决方案一样，样本数量是 O(k)，而不是列表元素数量的 O(n)。
这里的直觉是，我们可以跳过列表中的任意部分，而不需要访问它们，因为选择之间的元素数量与我们在列表中看到的数据无关。
与上面依赖超几何分布不同，水库是预先填充了候选解（前 k 个项目），并定期进行替换，这使得它看起来更像是一个具有几何等待时间的过程。这是一篇被广泛引用的论文，但我无法访问它以确认其证明在大 N 时是否渐近正确，或者是否适用于所有 N。
文章中并不清楚这个算法是否可以在开始时不知道序列长度的情况下使用（在这种情况下，可能可以直接使用本答案第一部分中的原始方法）。
以下代码会生成一个大小为4的随机样本：
import random
sample_size = 4
sorted_sample = [
mylist[i] for i in sorted(random.sample(range(len(mylist)), sample_size))
]
（注意：在Python 2中，最好使用xrange而不是range）
解释
random.sample(range(len(mylist)), sample_size)
这段代码生成了原始列表中元素的索引的随机样本。
这些索引会被排序，以保持原始列表中元素的顺序。
最后，列表推导式根据这些随机选出的索引，从原始列表中提取出实际的元素。