从列表中获取随机样本,同时保持项目的排序？

Question

我有一个排序列表,让我们说:(它不仅仅是数字,它是一个用复杂的耗时算法排序的对象列表)

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 ]

等等...

Answer 1

以下代码将生成大小为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)

生成原始列表的索引的随机样本.

然后对这些索引进行排序以保留原始列表中元素的顺序.

最后,给定采样索引,列表理解从原始列表中提取实际元素.

Answer 2

简单代码O(N + K*log(K))方式

取一个随机样本而不替换索引,对索引进行排序,并从原始索引中取出它们.

indices = random.sample(range(len(myList)), K)
[myList[i] for i in sorted(indices)]

或者更简洁:

[x[1] for x in sorted(random.sample(enumerate(myList),K))]

优化O(N)时间,O(1) - 辅助空间方式

您也可以使用数学技巧并myList从左到右迭代地进行,以动态变化的概率选择数字(N-numbersPicked)/(total-numbersVisited).这种方法的优点是它是一种O(N)算法,因为它不涉及排序!

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

概率证明和测试概率是正确的:

在5小时内用1万亿个伪随机样本模拟:

>>> Counter(
        tuple(orderedSampleWithoutReplacement([0,1,2,3], 2))
        for _ in range(10**9)
    )
Counter({
    (0, 3): 166680161, 
    (1, 2): 166672608, 
    (0, 2): 166669915, 
    (2, 3): 166667390, 
    (1, 3): 166660630, 
    (0, 1): 166649296
})

概率与真实概率的差异小于1.0001.再次运行此测试会导致不同的顺序,这意味着它不会偏向一个排序.使用较少的样本运行测试[0,1,2,3,4], k=3并[0,1,2,3,4,5], k=4获得类似的结果.

编辑:不确定为什么人们投票错误评论或害怕投票...不,这种方法没有错.=)

(也是评论中用户tegan的一个有用的注释:如果这是python2,你会像往常一样使用xrange,如果你真的关心额外的空间.)

编辑:证明:考虑到k从一个seq大小的群体中挑选一个子集的均匀分布(无需替换)len(seq),我们可以将任意点的分区视为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).

编辑:Timothy Shields提到了水库采样,这len(seq)是未知时这种方法的推广(例如使用生成器表达式).具体地,标记为"算法R"的那个是O(N)和O(1)空间,如果就地完成的话; 它涉及取第一个N元素并慢慢地替换它们(还给出了一个归纳证明的暗示).在维基百科页面上还可以找到有用的分布式变体和水库采样的各种变体.

编辑:这是另一种以更加语义明显的方式对其进行编码的方法.

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)

)

Answer 3

也许您只需生成索引样本,然后从列表中收集项目.

randIndex = random.sample(range(len(mylist)), sample_size)
randIndex.sort()
rand = [mylist[i] for i in randIndex]