Просмотр исходного текста страницы Методы получения случайных комбинаторных объектов

== Описание алгоритма ==
{{Задача
|definition = Необходимо сгенерировать случайный комбинаторный объект размера <tex> n </tex> с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
}}
Пусть <tex> B = \{b_1, b_2 ..., b_k\} </tex> - множество различных элементов, которые могут находиться в данном комбинаторном объекте.

Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны <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>
   '''for''' i = 1 '''to''' n                               
     s = number(prefix) <font color = green> // число комбинаторных объектов с текущим префиксом. </font>
     r = random(1, s)
     '''for''' j = 1 '''to''' k  
       '''if''' number(prefix + B[j]) < r <font color = green> // <tex> B </tex> {{---}} множество всех возможных элементов. </font>
         r = r - number(prefix + B[j]) <font color = green> // если <tex> r </tex> не попало в текщий диапазон {{---}} перейдем к следующему.</font>
       '''else''' 
         prefix[i] = b[j]
         break
   '''return''' prefix

Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.

=== Доказательство корректности ===
Докажем по индукции, что вероятность получить любой перфикс <tex> P </tex> равна <tex> C(n)\over{S(P)} </tex>, где <tex> C(n) </tex> - число различных комбинаторных данного типа длины <tex> n </tex>, а <tex> S(P) </tex> - число различных комбинаторных обьектов с таким префиксом.
*Любой комбинаторный объеут имеет пустой перфикс, следовательно <tex> S(\varnothing)=C(n) </tex>. Вероятность получить любой префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(\varnothing)\over{S(P)} </tex>, что равно <tex> C(n)\over{S(P)} </tex>.
*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна  <tex> C(n)\over{S(P)} </tex>
*Тогда вероятность получить из <tex> P </tex> любой префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> C(n)\over{S(P)} </tex><tex>\cdot</tex><tex> S(P)\over{S(P')} </tex> , что равно <tex> C(n)\over{S(P')} </tex>

== Битовые вектора ==
Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов одинаково и равно, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>

 '''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
   '''for''' i = 1 '''to''' n                               
     r = random(0, 1)
     v[i] = r
   '''return''' prefix

Сложность алгоритма {{---}} <tex> O(n) </tex>, так как в случае двоичных векторов <tex> k </tex> постоянно и равно <tex> 2 </tex>.

== Правильные скобочные последовательности ==
Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная пследовательность состоит  из двух типов элементов: открывающей и закрывающей скобок, следовательно <tex> k = 2 </tex>. 

Рассмотрим "полуправильные" скобочные последовательности т.е. такие что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты. Такую последовтеьность можно охарактеризовать двумя числами: <tex> l </tex> — длина скобочной последовательности и <tex> b </tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок). Заметим что любой префикс правильной скобочной последовательности является "полупраильной" скобочной последовательностью, и что для любого префикса <tex> P </tex> длины <tex> l </tex> число различных ПСП длины <tex> n </tex> равно числу "полуправильных" скобочных последовательностей длины <tex> n-l </tex> с таким же балансом как у <tex> P </tex>.

Научимся считать <tex> number(l, b) </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>). Если <tex> l = 0 </tex>, то ответ понятен сразу: <tex> number[0][0] = 1 </tex>, все остальные <tex> number[0][b] = 0 </tex>. Пусть теперь <tex> i > 0 </tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> '(' </tex>, то до этого символа мы находились в состоянии <tex> (l-1,b-1) </tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(l-1,b+1)</tex>. Таким образом, получаем формулу:

<tex>number[l][b] = number[l-1][b-1] + number[l-1][b+1]</tex>

(считается, что все значения <tex> number[l][b] </tex> при отрицательном <tex>j</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</tex>.

Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = number[n - l][b] </tex>) , будет разбиваться на два диапазона размерами <tex> number[n - l - 1][b + 1] </tex> и <tex> number[n - l - 1][b - 1] </tex> , и к префиксу будет прибавляться <tex>'('</tex> или <tex>')'</tex> если случайное число попало в первый или второй диапазон соответственно.

 '''string''' randomObject(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
     b = 0
     l = 0
   '''for''' i = 1 '''to''' n                               
     s = number[n - l][b] 
     r = random(1, s)
      '''if''' number[n - l - 1][b + 1] >= r
        l = l + 1
        b = b + 1
        result = result + '('
      '''else'''
        l = l + 1
        b = b - 1
        result = result + ')'
   '''return''' result

Итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет.

== Разбиения на множества ==
=== Разбиение на <tex> k </tex> подмножеств ===
Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, ..., n\} </tex>. Необходимо разбить его на <tex> k </tex> непустых подмножеств <tex> \{B_1, B_2, ..., B_k\} </tex> с равным распределением вероятности.
Будем строить разбиение таким образом, чтобы в результате подмножества <tex> \{B_1, B_2, ..., B_k\} </tex> оказались отсортированы в лексикографическом порядке(т.е. чтобы для любых <tex> 1 <= i < j <= k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_i </tex>).