Методы генерации случайного сочетания — различия между версиями
(→Псевдокод) |
|||
Строка 21: | Строка 21: | ||
sort(S); | sort(S); | ||
'''for''' i = 1 '''to''' k | '''for''' i = 1 '''to''' k | ||
− | C | + | C[i] = S[i] |
r = rand(1, n! / (k!(n - k)!)) | r = rand(1, n! / (k!(n - k)!)) | ||
'''for''' i = 1 '''to''' r - 1 | '''for''' i = 1 '''to''' r - 1 |
Версия 16:47, 16 декабря 2014
Задача: |
Необходимо сгенерировать случайное сочетание из | элементов по с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
Содержание
Решение за время
Пусть
— массив из элементов, тогда для генерации случайного сочетания сделаем следующее:- отсортируем ,
- запишем в массив первые элементов(это первое сочетание),
- выберем случайные номер сочетания ,
- применим алгоритм генерации следующего сочетания раз к массиву .
Псевдокод
randomCombination(S, n, k) sort(S); for i = 1 to k C[i] = S[i] r = rand(1, n! / (k!(n - k)!)) for i = 1 to r - 1 next_Combination(C, n, k) return res
Решение за время
Пусть
— множество из элементов, тогда для генерации случайного сочетания сделаем следующее:- выберем в множестве случайный элемент,
- добавим его в сочетание,
- удалим элемент из множества.
Эту процедуру необходимо повторить
раз.Псевдокод
randomCombination(arrayOfElements, n, k) for i = 1 to k r = rand(1..(n - i + 1)) cur = 0 for j = 1 to n if exist[j] cur++; if cur == r res[i] = arrayOfElements[j] exist[j] = false sort(res) return res
Здесь
— такой массив, что если , то элемент присутствует в множестве .Сложность алгоритма —
Доказательство корректности алгоритма
На первом шаге мы выбираем один элемент из
, на втором из , ..., на -ом из . Тогда общее число исходов получится . Это эквивалентно . Однако заметим, что на этом шаге у нас получаются лишь размещения из по . Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно размещений, то сочетания тоже генерируются равновероятно.Решение за время
Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив алгоритм генерации случайной перестановки. Тогда все элементы , для которых , включим в сочетание.
размера , состоящий из единиц и нулей. Применим к немуПсевдокод
randomCombination(arrayOfElements, n, k) for i = 1 to n if i <= k a[i] = 1 else a[i] = 0 random_shuffle(a) for i = 1 to n if a[i] == 1 ans.push(arrayOfElement[i]) return ans
Доказательство корректности алгоритма
Заметим, что всего перестановок
, но так как наш массив состоит только из и , то перестановка только или только ничего в нем не меняет. Заметим, что число перестановок нулей равно , единиц — . Следовательно, всего уникальных перестановок — . Все они равновероятны, так как была сгенерирована случайная перестановка, а каждой уникальной перестановке сопоставлено ровно перестановок. Но — число сочетаний из по . То есть каждому сочетанию сопоставляется одна уникальная перестановка. Следовательно, генерация сочетания происходит также равновероятно.Оценка временной сложности
Алгоритм состоит из 2 невложенных циклов по Фишера—Йетcа. Следовательно, сложность и всего алгоритма
итераций каждый и функции генерации случайной перестановки , работающей за по алгоритму