從數組中挑選隨機數

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]