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

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

#Логирование в GUI. (32325 hits)
#Подсветка синтаксиса. (31463 hits)
#Простая геометрическая и текстовая анимация. (400928 hits)
#Вычисление значения полинома. (62106 hits)
#Обновление нескольких записей таблицы. (32512 hits)
#Простая быстрая сортировка. (112809 hits)
#Преобразование целых чисел в битовый массив. (37625 hits)
#Добавление истории операций(undo&redo) в компонент. (39981 hits)
#Преобразование сумм из цифрового представления в строковое. (175688 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (116822 hits)
#Часики на js. (92939 hits)
#Обертки для массивов. (38882 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (38880 hits)
#Сравнение алгоритмов сортировки массива. (182121 hits)
#Валидация, динамическая проверка заполнения html форм. (209203 hits)
#"Липкие" окна. (32175 hits)
#Рисование куба. (59876 hits)
#Рисование Фрактала (листьев папоротника). (53162 hits)
#Вычисление минимального / максимального значения. (74392 hits)
#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (46241 hits)


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

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

Aвтор:
Дата:
Просмотров: 58609
реализации(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]