选择单个随机值组合的算法？

Question

说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.

请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.

如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.

Answer 1

Robert Floyd为这种情况发明了一种采样算法.它通常优于洗牌然后抓取第一个x元素,因为它不需要O(y)存储.如最初编写的那样,它假定来自1..N的值,但是通过简单地将它产生的值作为下标处理为向量/数组/其他来生成0..N和/或使用非连续值是微不足道的.

在pseuocode中,算法就像这样运行(从Jon Bentley的Programming Pearls专栏"Brilliance的样本"中窃取).

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

最后一点(如果T已经在S中则插入J)是棘手的部分.最重要的是,它确保插入J的正确数学概率,以便产生无偏的结果.

关于O(x)存储,它是O(x)¹和O(1).y

注意,根据问题中的组合标签,算法仅保证结果中出现的每个元素的概率相等,而不是它们在其中的相对顺序.

_{在最坏的情况下,所涉及的哈希映射可以忽略}¹ _{O(x ²),因为它是一个几乎不存在的病态情况,其中所有值都具有相同的哈希值}

Answer 2

假设您希望订单也是随机的(或者不介意它是随机的),我只会使用截断的Fisher-Yates shuffle.启动随机播放算法,但是一旦选择了第一个x值就停止,而不是"随机选择"所有y这些值.

Fisher-Yates的工作原理如下:

• 随机选择一个元素,并将其与数组末尾的元素交换.
• 递归(或更可能迭代)数组的其余部分,不包括最后一个元素.

第一步之后的步骤不要修改数组的最后一个元素.前两个步骤之后的步骤不会影响最后两个元素.第一个x之后的步骤不会影响最后的x个元素.所以在那时你可以停止 - 数组的顶部包含统一随机选择的数据.数组的底部包含一些随机元素,但是你得到的排列不是均匀分布的.

当然这意味着你已经破坏了输入数组 - 如果这意味着你需要在启动前获取它的副本,并且x与y相比较小,那么复制整个数组效率不高.请注意,如果您将来要使用它进一步选择,那么它有点随机顺序并不重要,您可以再次使用它.因此,如果您多次进行选择,则可以在开始时只进行一次复制,并分摊成本.