Изменения
Нет описания правки
{{Задача
|definition = Необходимо сгенерировать случайный [[Комбинаторные объекты|комбинаторный объект]] размера <tex> n </tex> с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
}}
== Описание алгоритма ==
{{Определение
|definition = '''[[Комбинаторные объекты]]''' (англ. ''combinatorial objects'') {{---}} конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
Пусть <tex> B = \{b_1, b_2 \ldots, b_k\} </tex> {{---}} множество различных элементов, которые могут находиться в данном комбинаторном объекте.
=== Битовые вектора ===
'''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
=== Правильные скобочные последовательности ===
{{Определение
|definition ='''[[Правильные скобочные последовательности|Правильная скобочная последовательность]]''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами: *<tex>\varepsilon</tex> (пустая строка) есть правильная скобочная последовательность;*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;}}Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная последовательность состоит из двух типов элементов: открывающей и закрывающей скобок, следовательно <tex> k = 2 </tex>. {{Определение|definition='''Полуправильная скобочная последовательность''' (анлг. ''Semi-Correct Bracket Sequence'') {{---}} скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты.
}}
Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: <tex> l </tex> — {{---}} длина скобочной последовательности и <tex> b </tex> — {{---}} баланс (т.е. разность между количеством открывающих и закрывающих скобок). Заметим что любой префикс правильной скобочной последовательности является полуправильной скобочной последовательностью, и что для любого префикса <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>. Таким образом, получаем формулу:
=== Разбиения на множества ===
{{Определение
|definition=[[Комбинаторные объекты#Разбиение на подмножества|'''Разбиение множества''' <tex>X</tex> '''на подмножества''']] (англ. ''Partition of a set'') {{---}} семейство непустых множеств <tex>\{U_{\alpha}\},{\alpha \in A}</tex>, где <tex>A</tex> {{---}} некоторое множество индексов, если:
# <tex>U_{\alpha} \cap U_{\beta} = \emptyset</tex> для любых <tex>\alpha, \beta \in A</tex>, таких что <tex>\alpha \not= \beta</tex>;
# <tex>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</tex>.
}}
==== Разбиение на <tex> k </tex> подмножеств ====
Рассмотрим множество первых <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> оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых <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> двумя способами:
*Добавить текущий элемент (<tex> n-l </tex>) в одно из <tex> k-m </tex> незаконченных подмножеств. В таком случае число обьектов с префиксом <tex> P' </tex> будет равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} </tex> .
*Сделать текущий элемент последним в подмножестве <tex> B_{k-m} </tex> . В таком случае это подмножество станет законченым, следовательно число обьектов с префиксом <tex> P' </tex> будет равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} </tex>.
