Построить алгоритм выбора случайного элемента из последовательности, чтобы каждый элемент мог оказаться выбранным с равной вероятностью
Разбор задачи с собеседования в Яндекс: за один проход выбрать случайный элемент последовательности так, чтобы каждый элемент мог быть выбран с равной вероятностью.
![Обложка поста Построить алгоритм выбора случайного элемента из последовательности, чтобы каждый элемент мог оказаться выбранным с равной вероятностью](https://media.tproger.ru/uploads/2017/02/pic0-2.png)
Пусть у нас есть некоторая конечная последовательность чисел и мы имеем итератор, указывающий на первый элемент. Мы можем при помощи итератора посмотреть значение текущего элемента и перейти к следующему элементу. Требуется построить такой алгоритм выбора случайного элемента из этой последовательности, чтобы каждый элемент мог оказаться выбранным с равной вероятностью.
Ограничения: мы можем использовать O(1) дополнительной памяти и не можем создавать новый итератор. Можно пользоваться функцией генерации случайного числа от [0;1).
Решение:
Создадим некоторую переменную, обозначим ее — x. Будем идти по последовательности и по ходу хранить номер элемента последовательности. Пусть мы сейчас находимся на элементе номер i, нумерация с 1. С вероятностью 1/i присвоим переменной x значение текущего элемента. Чтобы сделать действие с вероятностью p можем сгенерировать случайное число в диапазоне [0;1) и если сгенерированное число меньше p, то делаем действие, иначе не делаем.
Почему это работает?
Осталось доказать несложное утверждение: в переменной x после выполненных действий может оказаться любой элемент последовательности равновероятно, то есть каждый с вероятностью 1/n, где n число элементов последовательности.
Доказательство:
Будем доказывать по индукции. Для n=1 утверждение очевидно. Предположим, что утверждение верно для n=k, докажем его для n=k+1. После того, как мы выполним указанные действия для k первых элементов в переменной x находится одно из k чисел равновероятно, то есть с вероятностью 1/k каждое, по предположению индукции. После обработки (k+1)-го элемента вероятность того что в переменной x находится (k+1)-й элемент – 1/(k+1). Следовательно, вероятность того что в переменной x находится не (k+1)-й элемент – k/(k+1), а поскольку все k первых элементов были сохранены в переменной x равновероятно до обработки (k+1)-го элемента, то вероятность появления в переменной x любого из первых k элементов 1/(k+1). Таким образом утверждение доказано.
Если вам понравилась эта задачка, возможно, вам также понравится:
- Вы должны выбрать одну из двух ставок. При первом варианте вы должны забросить баскетбольный мяч в корзину. Если попадёте, то получите 50 тыс. рублей. Во втором варианте вам надо попасть два раза из трёх бросков, и тогда вы также получите те же 50 тыс. рублей. Какой из этих вариантов вы предпочтёте?
Разбор решения
10К открытий10К показов