algorithm - 从数组中选择随机数

Question

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

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

Answer 1

为 [nm,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]