Изменения
Нет описания правки
{{Задача
|definition = Необходимо сгенерировать случайный [[Комбинаторные объекты|комбинаторный объект]] размера <tex> n </tex> с равномерным распределением вероятности, если в наличии есть '''функция для генерации случайного числа в заданном интервале''' (англ. ''random number generator'').
}}
Пусть <tex> B = \{b_1, b_2 \ldots, b_k\} </tex> {{---}} множество различных элементов, которые могут находиться в данном комбинаторном объекте.
Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили '''префикс ''' (англ. ''prefix'') длинны <tex> i </tex> : <tex> P = \{a_1, a_2, \ldots, a_i\} </tex>. Будем выбирать элемент <tex> a_{i+1} </tex> из множества всех возможных так, чтобы вероятность выбора элемнта <tex> b \in B </tex>, была пропорциональна числу комбинторных обьектов размера <tex> n </tex> с префиксом <tex> P + b </tex>. Для этого разобъем отрезок натуральных чисел <tex> [1, s] </tex>. где <tex> s </tex> {{---}} число различных комбинаторных объектов с текущим префиксом, на <tex> k </tex> диапазонов так, чтобы размер диапазаона <tex> d_j </tex> был равен числу объектов с префиксом <tex> P + b_j </tex>. С помощью функции для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex> и добавим к префиксу <tex> P </tex> элемент <tex> b_j </tex> соответствующий диапазону отрезка в котором находится полученное число.
'''object''' randomObject(n: '''int''', k: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер комбинторного объекта, <tex> k </tex> {{---}} число различных элемнтов.</font>
=== Битовые вектора ===
Рассмотрим алгоритм получения случайного [[Комбинаторные объекты#Битовые вектора|битового вектора]] (англ. ''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 Sequencecorrect 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> 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> будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным).
