Изменения
→Примеры решения задач
=== Битовые вектора ===
Рассмотрим алгоритм получения случайного [[Комбинаторные объекты#Битовые вектора|битового вектора]](англ. ''Bit Vector''). В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов длины <tex> n </tex> одинаково и равно <tex> 2^{n-l} </tex>, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>
'''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
=== Правильные скобочные последовательности ===
Рассмотрим алгоритм получения случайной [[Правильные скобочные последовательности|правильной скобочной последовательности]](анлг. ''Correct Bracket Sequence''). Правильная скобочная последовательность состоит из двух типов элементов: открывающей и закрывающей скобок, следовательно <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> k </tex> подмножеств ====
Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, \ldots, n\} </tex>. Необходимо построить его [[Комбинаторные объекты#Разбиение на подмножества|разбить]] его разбиение на <tex> k </tex> непустых подмножеств ]] (анлг. ''Set Partition'') <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> будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным).
