Выбор случайных чисел из массива

Question

Можно ли выбрать M уникальных равномерно случайных элементов из массива размера N в O (M) времени?

Решение O (N), очевидно, тривиально, например. Fisher-Yates имеет размер N массива и усекает первые M элементов.

Answer 1

Выберите случайное число в [0, x) для каждого x из [n-m, n]. Для каждого случайного числа замените элемент по этому индексу на элемент в индексе верхней границы. Что-то вроде:

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]