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

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

#Вставка новой записи в таблицу БД. (31136 hits)
#Отслеживание изменений файла. (32683 hits)
#Рисование куба. (53186 hits)
#Вездесущий двоичный поиск.... (156530 hits)
#Относительный путь к файлу. (35063 hits)
#Случайный выбор нескольких несовпадающих значений из множества. (52493 hits)
#Простой генератор случайных чисел. (127144 hits)
#Хранение иерархических деревьев. (48492 hits)
#Курсы валют. (61990 hits)
#Рисование множества Мандельброта. (38658 hits)
#Валидация, динамическая проверка заполнения html форм. (201154 hits)
#Преобразование целых чисел в битовый массив. (32210 hits)
#Рисование тора. (29918 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (51623 hits)
#Вычисление медианы заданной выборки. (44277 hits)
#Сравнение алгоритмов быстрой сортировки. (66809 hits)
#Рисование прямоугольника. (26290 hits)
#Улучшение быстрой сортировки. (68422 hits)
#Простая быстрая сортировка. (104456 hits)
#Использование компилируемых(подготовленных) запросов. (25849 hits)


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



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

Aвтор:
Дата:
Просмотров: 52492
реализации(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 разных значений массива, code #82[автор:this]



© 2006-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.01505 секунд
Количество запросов к БД: 14, gzip: off