Выберите K случайных строк из текстового файла

Question

Это расширение исходного вопроса о выборе случайной строки из текста из X строк, где вероятность выбранной текстовой строки равна 1 / X.Хитрость заключается в выборе J-й строки, если вы запрашиваете случайную переменную Y с диапазоном [0,1), и она возвращает значение меньше 1 / Дж.

Теперь в этой новой версии задачи мыЯ должен выбрать K случайных линий, где K меньше X. Я считаю, что вероятность для каждой строки должна быть K / X.

Я застрял на том, как расширить исходное решение для K строк.Является ли это возможным?любые объяснения были бы великолепны.

Answer 1

Это можно решить, используя обобщение исходного алгоритма. Интуиция такова: ведите список из k строк-кандидатов из файла, которые изначально высеваются в первые k строк. Затем, начиная с этого момента, увидев n-ую строку файла:

• Выберите случайное значение x от 1 до n включительно.
• Если x> k, игнорировать этот элемент.
• В противном случае заменить элемент x на n-ю строку файла.

Доказательство того, что это правильно выбирает каждый элемент с вероятностью k / n, где n - общее количество строк в файле, заключается в следующем. Предположим, что n & ge; к. По индукции мы доказываем, что каждый элемент имеет вероятность k / n выбора, показывая, что после просмотра z элементов каждый из этих элементов имеет вероятность выбора k / z. В частности, это означает, что после просмотра n элементов каждый имеет вероятность k / n, как требуется.

В качестве нашей индуктивной основы, если мы видим ровно k элементов, то выбирается каждый. Таким образом, вероятность быть выбранной k / k, как требуется.

Для индуктивного шага предположим, что для некоторого z & ge; k, каждый из первых z элементов был выбран с вероятностью k / z и рассмотрим (z + 1) -й элемент. Выбираем случайное натуральное число в диапазоне [1, z + 1]. С вероятностью k / (z + 1) мы решили выбрать этот элемент, а затем выселить какой-то старый элемент. Это означает, что новый элемент выбран с вероятностью k / (z + 1). Для каждого из z исходных элементов вероятность того, что он будет выбран в этой точке, представляет собой вероятность того, что мы выбрали его после проверки первых z элементов (вероятность k / z, согласно нашей индуктивной гипотезе), и вероятность того, что мы сохранить это z / (z + 1), так как мы заменяем его с вероятностью 1 / (z + 1). Таким образом, новая вероятность того, что она выбрана, равна (k / z) (z / (z + 1)) = k / (z + 1). Таким образом, все первые элементы z + 1 выбираются с вероятностью k / (z + 1), что завершает индукцию.

Кроме того, этот алгоритм выполняется за время O (n) и использует только пространство O (k), что означает, что время выполнения не зависит от значения k. Чтобы увидеть это, обратите внимание, что каждая итерация выполняет O (1), и существует всего O (n) взаимодействий.

Если вам интересно, у меня есть реализация этого алгоритма в виде алгоритма в стиле C ++ STL , доступная здесь на моем персональном сайте .

Надеюсь, это поможет!

Answer 2

Сначала выберите первый элемент случайным образом из X строк, используя первый алгоритм. Затем выберите вторую из оставшихся строк X-1. Запустите этот процесс K раз.

Вероятность любого данного набора из K линий равна (X choose K). Я предоставлю вам возможность убедиться, что этот алгоритм дает желаемое равномерное распределение.