Как выбрать один из n объектов наугад, не зная поначалу?

Question

Для конкретности, как бы вы прочитали текстовую строку, а также выбрали и напечатали одну случайную строку, если вы не знаете заранее количество строк?

Да, это проблема из жемчужины программирования,Я запутался.

Решение выбрать 1-й элемент, затем выбрать второй с вероятностью 1/2, третий с 1/3 и т. Д.

Алгоритм:

i = 0
while more input lines
  with probability 1.0/++i
    choice = this input line
 print choice

Предположим, что окончательным выбором является 3-й элемент, вероятность составляет 1 x 1/2 x 1/3 x 3/4 x ... x n-2 / n-1 xn-1 / n == 1 / 2n?Но 1 / n должно быть правильным.

Answer 1

Ваш алгоритм правильный, но анализ - нет. Вы можете доказать это по индукции. Свободно: это работает для N = 1, конечно. Если он работает до N-1, то что происходит в N? Вероятность того, что N-й элемент выбран и перезаписан последний вариант, равна 1 / N - хорошо. Вероятность того, что это не так (N-1) / N. В этом случае используется выбор из предыдущего шага. Но в этот момент все элементы имели 1 / (N-1) шанс быть выбранным. Теперь это 1 / N. Хорошо.

Answer 2

Ваш расчет неверен:

Предположим, окончательный выбор - 3-й элемент, вероятность 1 х 1/2 х 1/3 х 3/4 х ... х н-2 / н-1 х н-1 / н

Реальная вероятность:

(1 x 1/2 + 1 x 1/2) x 1/3 x 3/4 x ... x n-2 / n-1 x n-1 / n == 1 / n

поскольку вы либо выбрали 2, либо не выбрали 2 (выбор 2 имеет вероятность 1/2, а не выбор 2 - 1/2)

Answer 3

Чтение 1 Читать 2 Шанс 50% любого, оставь один, откажись от одного. Читать 3 (у нас должно быть 1 и 3 или 2 и 3). 50% -й шанс одной из линий отбросить другую. Продолжайте работать с 50% -ной вероятностью на протяжении всего файла, это оставляет вам 2 строки Возьмите 50/50 на любой из линий, и вы получите случайную линию. Шансы были одинаковыми для всего файла.

Answer 4

Это не совсем случайный случай - вы, скорее всего, выберете строку в начале файла. Вам нужно знать количество строк, чтобы сделать его случайным. (50% времени вы получаете первую строку!)