从列表中的随机项目

这更像是一个谜题。我想知道是否有一种方法可以从n个项目列表中选择k个随机项目，因为n是未知的，我只想读取一次项目列表。从列表中的随机项目

谢谢

2010-11-27 Bob

如果`K> = N`？你会得到所有物品吗？ – 2010-11-27 01:25:54

取第一个k，因为你不知道他们是随机的:) – 2010-11-27 01:28:32

n是未知的;然而，假设k <= n成立。前k项不是随机的，它可能是一个排序列表。 – Bob 2010-11-27 01:38:46

我猜的答案，我的问题是这样的：

pick first k elements and store them into an array of length k 
for each element x > k 
    insert x with probability k/x 
    choose position at random between 1 and k

来源

2010-11-28 01:50:36 Bob

简单（如果k < = n）。这就像获得k个号码列表< n。这将是要获得的数字位置的列表。创建范围列表（0..n），从中获得k个随机数。直到最后一刻，您不必阅读物品的实际列表。显然，这只是有用的是最后的项目列表是慢读（它是从磁盘或类似的东西读取）。

为了获得项目的位置，只选择做：

import random 
itemstopick = random.Random().sample(range(0,n), k)

如果n，项目数是未知的，那么你必须开始采摘第k个项目（即解决方案如果k = n）。然后，唯一的选择是继续阅读物品，并选择保留刚刚阅读的新物品（并删除另一个物品）或保持当前物品的状态。要坚持一致的概率，您将不得不降低选择最后一个读取项目的概率。保持最后一项的概率应该总是P（k/n0），其中n0是当时n的值。我不相信你能做得比这更好。

如果你知道一些n的大小（值可以保证n大于它），只需要混合上面的两个方法即可。首先用一个用minorant而不是n创建的列表，然后像未知n那样继续。

来源

2010-11-27 01:31:55 kriss

这取决于你是否有随机值生成，如果你这样做，比可能，如果不是你将不得不生成它们，你将需要从2 * k到3 * k左右的操作这种情况下，

来源

2010-11-27 01:37:56 Lu4

跳过随机数从当前位置的项目列表
就拿当前项目。
如果您已到达列表的末尾，请跳到列表的开头并转到步骤1
重复这些步骤k次。

来源

2010-11-27 02:08:26 codymanix

从列表中的随机项目

回答

相关问题