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

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

#Наибольший общий делитель. (188060 hits)
#Поразрядная сортировка массива подсчетом. (129643 hits)
#Просмотр изображения во всплывающем окне. (86648 hits)
#Улучшение быстрой сортировки. (73283 hits)
#Выборка всех записей таблицы. (31226 hits)
#Добавление истории операций(undo&redo) в компонент. (37903 hits)
#Постепенное затемнение. (49125 hits)
#Шифрование произвольных данных. (323500 hits)
#Создание нестандартного (custom-ного) окна браузера. (34153 hits)
#Преобразование целых чисел в битовый массив. (35362 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (140289 hits)
#Валидация, динамическая проверка заполнения html форм. (206135 hits)
#Создание простейшей таблицы. (35156 hits)
#Доступ ко всем полям и методам. (55939 hits)
#Динамическое формирование выпадающего списка. (49300 hits)
#Масштабирование, пропорциональное изменение размеров картинки. (95749 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (29249 hits)
#Рисование Фрактала (листьев папоротника). (50783 hits)
#Бинарный поиск в массиве и его разновидности. (161385 hits)
#Вычисление медианы заданной выборки. (47478 hits)


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

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

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