CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Летающие, крутящиеся шарики. (44548 hits)
#Вычисление значения полинома. (62104 hits)
#Сравнение алгоритмов сортировки массива. (182106 hits)
#Динамическая очистка выпадающего списка (select) на javascript. (90864 hits)
#Рисование 3D объекта. (35138 hits)
#Сортировка вставкой. (112196 hits)
#Сортировка выбором, общий подход. (72845 hits)
#Рисование окружности (по Брезенхэму). (33874 hits)
#Относительный путь к файлу. (39741 hits)
#Найти максимальную сумму в последовательности. (137245 hits)
#сортировка пузырьком. (152821 hits)
#Постраничный вывод. (72723 hits)
#Наибольший общий делитель. (192516 hits)
#Постепенное затемнение. (51349 hits)
#Рисование линии (по Брезенхэму). (34045 hits)
#Последовательный поиск и его оптимизации. (44736 hits)
#Рисование полусферы. (29028 hits)
#Подсветка синтаксиса. (31461 hits)
#Пирамидальная сортировка. (203698 hits)
#Случайный выбор элемента при неизвестном их количестве. (36694 hits)


Главная >> Каталог задач >> Числа >> Случайные числа >>

Случайный выбор нескольких несовпадающих значений из множества

Aвтор:
Дата:
Просмотров: 58606
реализации(C#: 1шт...) +добавить

На вход программы подается два целых числа: m и n, причем m < n. На выходе должен получаться список из m случайных целых чисел в диапазоне 0..n-1, причем никакое число не должно встретиться дважды. Сточки зрения теории вероятностей, мы должны реализовать выбор без возврата, причем вероятность выбора всех элементов должна быть одинакова.

Красивый интересный алгоритм решения данной задачи, выдвинутый еще Кнутом.

По книге Джона Бентли:
"Жемчужины программирования"

"...

Задача

Дело было в начале 80-х. Компания только что приобрела первые персональные компьютеры. Установив и настроив основные программы, я рекомендовал сотрудникам искать возможности автоматизации офисных задач с помощью новых машин. Фирма занималась опросами общественного мнения, и одна из сотрудниц предложила автоматизировать задачу выбора случайных представителей из списка избирательных участков. Поскольку решение задачи вручную требовало часа работы с таблицей случайных чисел, сотрудница предложила следующую программу:

На вход подается список названий участков и целое число m. На выходе должен получиться список из m случайно выбранных избирательных участков. В исходном списке обычно присутствует несколько сотен названий (каждое из которых представляет собой строку длиной не более десятка символов), а m обычно лежит в интервале 20...40.

Так представляла себе программу одна из пользователей Хотите ли вы высказать какие-нибудь предложения по формулировке задачи до того, как мы попытаем ее реализовать программно?

Я ответил сотруднице, что это замечательная идея. Задача отлично подходила для автоматизации. Затем я отметил, что набрать несколько сотен имен, возможно, проще, чем работать с большой таблицей случайных чисел, но это все равно утомительное занятие, в процессе которого легко наделать ошибок. Да и вообще глупо вводить кучу данных, если все равно большая их часть использована не будет. Поэтому я предложил поставить задачу в альтернативной форме.

На вход программы подается два целых числа: m и n, причем m < n. На выходе должен получаться список из m случайных целых чисел в диапазоне 0..n-1, причем никакое число не должно встретиться дважды. С точки зрения теории вероятностей, мы должны реализовать выбор без возврата, причем вероятность выбора всех элементов должна быть одинакова.

Для m = 20 и n = 200 программа должна выдать список из 20 чисел, который может начинаться, к примеру, так: 4, 15, 17,... Пользователь может выбрать 20 случайных названий из списка избирательных округов, в котором этих округов 200, отсчитывая их от начала списка и помечая 4, 15, 17-е и последующие. Числа на выходе должны быть отсортированы, потому что список на бумаге не пронумерован.

Эта спецификация была встречена с энтузиазмом со стороны потенциальных пользователей. После написания программы они получали бы возможность за несколько минут делать то, на что раньше требовался бы час.

Взгляните на задачу с другой стороны: как бы вы ее решили? Предположим, у вас есть функция bigrand(), возвращающая большое случайное целое число (много большее m и n) и функция randint(i, j), возвращающая случайное число из интервала i..j (с однородным распределением).

Одно из решений

Как только мы выяснили детали задачи, которую предстояло решить, я побежал за томом «Получисленных алгоритмов» Кнута (иметь дубликаты всех трех томов Кнута дома и на работе стоит затраченных денег). Поскольку за некоторое время до того я изучил эту книгу весьма внимательно, мне смутно припоминались алгоритмы для решения подобных задач. Потратив несколько минут на изучение нескольких подходящих алгоритмов решения задачи, я понял, что алгоритм S в разделе 3.4.2 был идеальным для решения моей задачи.

В алгоритме последовательно рассматривается каждое из чисел 0,1, 2,..., n-1, и каждое из них может быть выбрано, если оно случайным образом пройдет некоторую проверку. Последовательным перебором чисел мы гарантируем, что результат окажется отсортирован.

Чтобы понять критерий отбора, рассмотрим пример с m = 2 и n = 5. Мы выбираем первое число 0 с вероятностью 2/5. Программно это реализуется следующим образом:

 псевдокод: имитация события с вероятностью 2/5  ссылка
  1. if (bigrand() % 5) < 2


К сожалению, мы не можем установить ту же вероятность для числа 1, потому что в этом случае мы можем и не получить 2 числа из пяти (а можем и получить). Поэтому мы несколько изменим ситуацию, установив для единицы вероятность выбора 1/4, если 0 был выбран, и 2/4, если 0 не был выбран. В общем, чтобы получить s элементов из r оставшихся, мы будем выбирать очередной элемент с вероятностью s/r. Вот программа на псевдокоде:

 псевдокод: Выбор s случайных элементов из r оставшихся  ссылка
  1. select = m
  2. remaining = n
  3. for i = 0 to n-1
  4. if (bigrand() % remaining) < select
  5. print i
  6. select--
  7. remaining--


Пока m <= n программа всегда выбирает ровно m чисел. Большее количество выбрано быть не может, поскольку вероятность выбора очередного элемента становится нулевой, как только m чисел уже набрано. Меньше их тоже оказаться не может, потому что когда отношение требуемых к оставшимся становится равным 1, все оставшиеся числа однозначно проходят тест. Оператор for гарантирует, что числа будут выводиться в нужном порядке. Моего описания вам должно быть достаточно, чтобы поверить в равновероятность выбора любого набора чисел. Кнут доказывает это с помощью теории вероятностей.

Второй том Кнута очень облегчил мне задачу. Даже вместе с заголовком, вводом, выводом, проверкой ограничений и тому подобное, конечный вариант программы занимал всего 13 строк на языке BASIC. Он был готов спустя полчаса после постановки задачи и использовался много лет без каких-либо проблем. Вот эта программа:

 псевдокод: выбор m случайных несовпадающих чисел  ссылка
  1. function genknuth(m, n)
  2. for i = 0 to n-1
  3. /* выбор m из оставшихся n-i */
  4. if (bigrand() % (n-i)) < m
  5. print i
  6. m--


Программе требовалось всего несколько десятков байт памяти, и она была быстрой как молния (с учетом задач фирмы). Однако этот код может показаться медленным, если n будет слишком велико. Получение нескольких случайных 32-разрядных целых чисел (n = 232) требует на моем компьютере около 12 минут.

Реализации:

C#(1)   +добавить

1) Случайный выбор m разных значений массива на C#, code #82[автор:this]