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