Изменения
Нет описания правки
{{Задача
|definition = Необходимо сгенерировать случайный [[Комбинаторные объекты|комбинаторный объект]] размера <tex> n </tex> с равномерным распределением вероятности, если в наличии есть '''функция для генерации случайного числа в заданном интервале''' (англ. ''random number generator'').
}}
'''Переход:''' Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> \dfrac{S(P)}{C(n)} </tex>. Вероятность получить из <tex> P </tex> некоторый префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> \dfrac{S(P')}{S(P)} </tex> , следовательно вероятность получить
префикс <tex> P' </tex> равна <tex> \dfrac{S(P)}{C(n)} </tex><tex>\cdot</tex><tex> \dfrac{S(P')}{S(P)} </tex> что равно <tex> \dfrac{S(P')}{C(n)} </tex>.
}}
|definition='''Полуправильная скобочная последовательность''' (анлг. ''Semi-correct bracket sequence'') {{---}} скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты.
}}
Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: <tex> l </tex> — длина скобочной последовательности и <tex> b </tex> — '''баланс''' (англ. ''balance'') {{---}} разность между количеством открывающих и закрывающих скобок. Заметим что любой префикс правильной скобочной последовательности является полуправильной скобочной последовательностью, и что для любого префикса <tex> P </tex> длины <tex> l </tex> число различных правильных скобочных последовательностей длины <tex> n </tex> равно числу полуправильных скобочных последовательностей длины <tex> n-l </tex> с таким же балансом как у <tex> P </tex>.
Научимся считать <tex> D[l][b] </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>. Если <tex> l = 0 </tex>, то ответ понятен сразу: <tex> D[0][0] = 1 </tex>, все остальные <tex> D[0][b] = 0 </tex>. Пусть теперь <tex> l > 0 </tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> '(' </tex>, то до этого символа мы находились в состоянии <tex> (l-1,b-1) </tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(l-1,b+1)</tex>. Таким образом, получаем формулу:
<tex>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>
(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</tex>.
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = D[n-l][b] </tex>) , будет разбиваться на два диапазона размерами <tex> D[n-l-1][b+1] </tex> и <tex> D[n-l-1][b-1] </tex> , и к префиксу будет прибавляться <tex>'('</tex> или <tex>')'</tex> если случайное число попало в первый или второй диапазон соответственно.
s = D[n - l][b]
r = random(1, s)
'''if''' D[n - l - 1][b + 1] <tex> \geqslant </tex>= r
l = l + 1
b = b + 1
'''return''' result
=== Разбиения на множества ===
Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, \ldots, n\} </tex>. Необходимо построить его [[Комбинаторные объекты#Разбиение на подмножества|разбиение на <tex> k </tex> непустых подмножеств]] <tex> \{B_1, B_2, \ldots, B_k\} </tex> с равным распределением вероятности.
Будем строить разбиение таким образом, чтобы в результате подмножества <tex> \{B_1, B_2, \ldots, B_k\} </tex> оказались отсортированы в '''лексикографическом порядке''' (англ. ''lexicographical order'') (т.е. чтобы для любых <tex>i, j \mid 1 \leqslant i < j \leqslant k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_j </tex>). Для этого будем по очереди добавлять каждое число от <tex> n </tex> до <tex> 1 </tex> в одно из подмножеств и для каждого из подмножеств начиная с <tex> B_n </tex> и заканчивая <tex> B_1 </tex> будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным).
На каждом шаге префиксом считаем текущее разбиение. Оно характеризуется двумя значениями: <tex> l </tex> — число добавленных элементов и <tex> m </tex> — число подмножеств для которых определен последний элемент. Заметим, что количество разбиений на подмножества с заданным префиксом равно числу способов разбить еще не добавленные элементы на еще не законченные подмножества так, чтобы они оказались лексикографически упорядочены, то есть равно числу разбиений <tex> n-l </tex> элементов на <tex> k-m </tex> непустых подмножеств, что равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} </tex> ([[Числа Стирлинга второго рода|числу Стирлинга второго рода]]). Таким образом из префикса <tex> P </tex> мы можем получить следующий префикс <tex> P' </tex> двумя способами:
s = stirling(n - l, k - m) <font color = green> // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. </font>
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) <tex> \geqslant </tex>= r
result[i] = k - m <font color = green> // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. </font>
l = l + 1
