algorithm - 从数组中选取随机数

Question

是否可以在 O(M) 时间内从大小为 N 的数组中选取 M 个唯一的均匀随机元素？

O(N) 的解决方案显然是微不足道的，例如。 Fisher-Yates 大小为 N 的数组并截断为前 M 个元素。

Answer 1

为 [n-m,n] 中的每个 x 在 [0,x) 中选择一个随机数。对于每个随机数，将该索引处的项目与上限索引处的项目交换。像这样的东西:

import random

def random_elements(items, count):
    length = len(items)

    for i in range(count):
        index = random.randrange(0, length - i)
        yield items[index]
        items[length - i - 1], items[index] = items[index], items[length - i - 1]