Методы получения случайных комбинаторных объектов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Правильные скобочные последовательности)
м (rollbackEdits.php mass rollback)
 
(не показано 58 промежуточных версий 9 участников)
Строка 1: Строка 1:
== Описание алгоритма ==
 
 
{{Задача
 
{{Задача
|definition = Необходимо сгенерировать случайный комбинаторный объект размера <tex> n </tex> с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
+
|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> соответствующий диапазону отрезка в которм находится полученное число.
+
== Описание алгоритма ==
 +
Пусть <tex> B = \{b_1, b_2 \ldots, 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>
 
  '''object''' randomObject(n: '''int''', k: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер комбинторного объекта, <tex> k </tex> {{---}} число различных элемнтов.</font>
Строка 21: Строка 22:
 
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
 
Сложность алгоритма {{---}} <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>.
+
|statement=Вероятность получить в процессе работы алгоритма некоторый префикс <tex> P </tex> равна <tex> \dfrac{S(P)}{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна  <tex> C(n)\over{S(P)} </tex>
+
|proof=Докажем по [[Математическая индукция|индукции]]:
*Тогда вероятность получить из <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> \varnothing </tex>), следовательно <tex> S(\varnothing)=C(n) </tex>.
Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов одинаково и равно, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>
+
Вероятность получить некоторый префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> \dfrac{S(P)}{S(\varnothing)} </tex>, что равно <tex>
 +
\dfrac{S(P)}{C(n)} </tex> .
 +
 
 +
'''Переход:''' Пусть вероятность получить префикс <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>.
 +
}}
 +
 
 +
{{Утверждение
 +
|statement=Результатом работы данного алгоритма является случайный комбинаторный объект размера <tex> n </tex>, причем вероятность получения одинакова для каждого результата.
 +
|proof=Заметим, что результатом работы данного алгоритма является любой из возможных префиксов размера <tex> n </tex>. Любой такой префикс является комбинаторным объектом размера <tex> n </tex> и наоборот, следовательно число объектов с таким префиксом равно <tex> 1 </tex>. Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна <tex> \dfrac{1}{C(n)} </tex>.
 +
}}
 +
 
 +
== Примеры решения задач ==
 +
Рассмотрим примеры использования данного алгоритма для генерации различных типов комбинаторных объектов.
 +
 
 +
=== Битовые вектора ===
 +
Рассмотрим алгоритм получения случайного [[Комбинаторные объекты#Битовые вектора|битового вектора]]. В битовом векторе может находиться только два типа элементов: <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>
 
  '''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
Строка 38: Строка 54:
 
Сложность алгоритма {{---}} <tex> O(n) </tex>, так как в случае двоичных векторов <tex> k </tex> постоянно и равно <tex> 2 </tex>.
 
Сложность алгоритма {{---}} <tex> O(n) </tex>, так как в случае двоичных векторов <tex> k </tex> постоянно и равно <tex> 2 </tex>.
  
== Правильные скобочные последовательности ==
+
=== Правильные скобочные последовательности ===
Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная пследовательность состоит  из двух типов элементов: открывающей и закрывающей скобок, следовательно <tex> k = 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>.
+
|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> 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> 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>number[l][b] = number[l-1][b-1] + number[l-1][b+1]</tex>
+
<tex>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>
  
(считается, что все значения <tex> number[l][b] </tex> при отрицательном <tex>j</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</tex>.
+
(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</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> если случайное число попало в первый или второй диапазон соответственно.
+
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <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> если случайное число попало в первый или второй диапазон соответственно.
  
  '''string''' randomObject(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
+
  '''string''' randomBracketSequence(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
    b = 0
+
  b = 0
    l = 0
+
  l = 0
 
   '''for''' i = 1 '''to''' n                               
 
   '''for''' i = 1 '''to''' n                               
     s = number[n - l][b]  
+
     s = D[n - l][b]  
 
     r = random(1, s)
 
     r = random(1, s)
       '''if''' number[n - l - 1][b + 1] >= r
+
       '''if''' D[n - l - 1][b + 1] <tex> \geqslant </tex> r
 
         l = l + 1
 
         l = l + 1
 
         b = b + 1
 
         b = b + 1
Строка 67: Строка 85:
 
   '''return''' result
 
   '''return''' result
  
Итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет.
+
Итоговая сложность алгоритма {{---}} <tex> O(n) </tex>. Преподсчет <tex> D </tex> можно выполнить динамически за <tex> O(n^2) </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>.
 +
Таким образом на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = </tex><tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} </tex>) , будет разбиваться на два диапазона размерами <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} </tex>
 +
и <tex> (k-m)\cdot\genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} </tex>. Если случайно сгенерированное число попадет в первый диапазон, то сделаем <tex> n-l </tex> последним элементом в подмножестве <tex> B_{k-m} </tex> . Иначе добавим <tex> n-l </tex> в случайно выбранное из незаконченных подмножеств (<tex> \{B_1, B_2, \ldots, B_{k-m}\} </tex>).
 +
 
 +
'''int[]''' randomSetPartition(n: '''int''' k: '''int'''): <font color = green> // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. </font>
 +
  l = 0
 +
  m = 0
 +
  '''downto''' i = n '''to''' 1                             
 +
    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
 +
        m = m + 1
 +
      '''else'''
 +
        p = random(1, k - m) <font color = green> // Случайным образом выбираем номер одного из незаконченных подмножеств. </font>
 +
        result[i] = p
 +
        l = l + 1
 +
  '''return''' result
 +
 
 +
Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона, а всего шагов {{---}} <tex> n </tex> то итоговая сложность алгоритма {{---}} <tex> O(n) </tex> . Сложность преподсчета чисел Стирлинга второго рода {{---}} <tex> O(n^2) </tex> если преподсчитать их [[Динамическое программирование | динамически]].
 +
 
 +
==== Разбиение на случайное число подмножеств ====
 +
Описаный алгоритм можно применить для получения разбиения множества на случайное число подмножеств. Для этого достаточно случайным образом выбрать число подмножеств из интевала <tex> [1, n] </tex> , так чтобы вероятность получить число <tex> k </tex> была пропорциональна числу способов разбить <tex> n </tex> элементов на <tex> k </tex> подмножеств (что равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{k} </tex>).
 +
 
 +
Разделим интервал случайных чисел <tex> [1, s] </tex> (где <tex> s = </tex> <tex dpi="180"> \sum\limits_{i=1}^{n}{\genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i}}</tex>) на <tex> n </tex> диапазонов, так чтобы размер диапазона <tex> d_i </tex> был равен<tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i} </tex>. С помощью функции для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex>. Возьмем <tex> k </tex> такое, что <tex> r \in d_k </tex> и построим случайное разбиение множества из <tex> n </tex> элементов на <tex> k </tex> подмножеств.
 +
 
 +
== См. также ==
 +
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Метод генерации случайной перестановки]]
 +
*[[Методы генерации случайного сочетания|Методы генерации случайного сочетания]]
 +
 
 +
== Источники информации ==
 +
*Комбинаторные алгоритмы: учебное пособие / Т. И. Федоряева. {{---}} Новосибирск: Новосибирский гос. ун-т, 2011. 118 с. {{---}} ISBN 978-5-4437-0019-9
 +
*Non-Uniform Random Variate Generation / Luc Devroye. {{---}} Springer, New York, NY, 1986. 843 c. {{---}} ISBN 978-1-4613-8645-2
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]

Текущая версия на 19:44, 4 сентября 2022

Задача:
Необходимо сгенерировать случайный комбинаторный объект размера [math] n [/math] с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.


Описание алгоритма

Пусть [math] B = \{b_1, b_2 \ldots, b_k\} [/math] — множество различных элементов, которые могут находиться в данном комбинаторном объекте.

Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны [math] i [/math] : [math] P = \{a_1, a_2, \ldots, a_i\} [/math]. Будем выбирать элемент [math] a_{i+1} [/math] из множества всех возможных так, чтобы вероятность выбора элемнта [math] b \in B [/math], была пропорциональна числу комбинторных обьектов размера [math] n [/math] с префиксом [math] P + b [/math]. Для этого разобъем отрезок натуральных чисел [math] [1, s] [/math]. где [math] s [/math] — число различных комбинаторных объектов с текущим префиксом, на [math] k [/math] диапазонов так, чтобы размер диапазаона [math] d_j [/math] был равен числу объектов с префиксом [math] P + b_j [/math]. С помощью функции для генерации случайного числа получим число [math] r [/math] в интервале [math] [1, s] [/math] и добавим к префиксу [math] P [/math] элемент [math] b_j [/math] соответствующий диапазону отрезка в котором находится полученное число.

object randomObject(n: int, k: int):  // [math] n [/math] — размер комбинторного объекта, [math] k [/math] — число различных элемнтов.
  for i = 1 to n                               
    s = number(prefix)  // число комбинаторных объектов с текущим префиксом. 
    r = random(1, s)
    for j = 1 to k  
      if number(prefix + B[j]) < r  // [math] B [/math] — множество всех возможных элементов. 
        r = r - number(prefix + B[j])  // если [math] r [/math] не попало в текщий диапазон — перейдем к следующему.
      else 
        prefix[i] = b[j]
        break
  return prefix

Сложность алгоритма — [math]O(nk) [/math]. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.

Доказательство корректности

Лемма:
Вероятность получить в процессе работы алгоритма некоторый префикс [math] P [/math] равна [math] \dfrac{S(P)}{C(n)} [/math], где [math] C(n) [/math] — число различных комбинаторных объектов данного типа длины [math] n [/math], а [math] S(P) [/math] — число различных комбинаторных обьектов длины [math] n [/math] с таким префиксом.
Доказательство:
[math]\triangleright[/math]

Докажем по индукции:

База: Заметим, что любой комбинаторный объект имеет пустой префикс ([math] \varnothing [/math]), следовательно [math] S(\varnothing)=C(n) [/math]. Вероятность получить некоторый префикс [math] P [/math] длины [math] 1 [/math] равна [math] \dfrac{S(P)}{S(\varnothing)} [/math], что равно [math] \dfrac{S(P)}{C(n)} [/math] .

Переход: Пусть вероятность получить префикс [math] P [/math] длины [math] l [/math] равна [math] \dfrac{S(P)}{C(n)} [/math]. Вероятность получить из [math] P [/math] некоторый префикс [math] P' [/math] длины [math] l+1 [/math] равна [math] \dfrac{S(P')}{S(P)} [/math] , следовательно вероятность получить

префикс [math] P' [/math] равна [math] \dfrac{S(P)}{C(n)} [/math][math]\cdot[/math][math] \dfrac{S(P')}{S(P)} [/math] что равно [math] \dfrac{S(P')}{C(n)} [/math].
[math]\triangleleft[/math]
Утверждение:
Результатом работы данного алгоритма является случайный комбинаторный объект размера [math] n [/math], причем вероятность получения одинакова для каждого результата.
[math]\triangleright[/math]
Заметим, что результатом работы данного алгоритма является любой из возможных префиксов размера [math] n [/math]. Любой такой префикс является комбинаторным объектом размера [math] n [/math] и наоборот, следовательно число объектов с таким префиксом равно [math] 1 [/math]. Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна [math] \dfrac{1}{C(n)} [/math].
[math]\triangleleft[/math]

Примеры решения задач

Рассмотрим примеры использования данного алгоритма для генерации различных типов комбинаторных объектов.

Битовые вектора

Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: [math] 0 [/math] и [math] 1 [/math], следовательно [math] k = 2 [/math]. Заметим что для любого префикса длины [math] l [/math] число возможных комбинаторных объектов длины [math] n [/math] одинаково и равно [math] 2^{n-l} [/math], следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью [math] 0 [/math] или [math] 1 [/math]

vector<int> randomBitVector(n: int):  // [math] n [/math] — размер битового вектора.
  for i = 1 to n                               
    r = random(0, 1)
    v[i] = r
  return prefix

Сложность алгоритма — [math] O(n) [/math], так как в случае двоичных векторов [math] k [/math] постоянно и равно [math] 2 [/math].

Правильные скобочные последовательности

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

Определение:
Полуправильная скобочная последовательность (англ. Semi-correct bracket sequence) — скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки могут быть закрыты.

Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: [math] l [/math] — длина скобочной последовательности и [math] b [/math] — баланс — разность между количеством открывающих и закрывающих скобок. Заметим что любой префикс правильной скобочной последовательности является полуправильной скобочной последовательностью, и что для любого префикса [math] P [/math] длины [math] l [/math] число различных правильных скобочных последовательностей длины [math] n [/math] равно числу полуправильных скобочных последовательностей длины [math] n-l [/math] с таким же балансом как у [math] P [/math].

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

[math]D[l][b] = D[l-1][b-1] + D[l-1][b+1][/math]

(считается, что все значения [math] D[l][b] [/math] при отрицательном [math]b[/math] равны нулю).

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

string randomBracketSequence(n: int):  // [math] n [/math] — длина скобочной последовательности. 
  b = 0
  l = 0
  for i = 1 to n                               
    s = D[n - l][b] 
    r = random(1, s)
     if D[n - l - 1][b + 1] [math] \geqslant [/math] r
       l = l + 1
       b = b + 1
       result = result + '('
     else
       l = l + 1
       b = b - 1
       result = result + ')'
  return result

Итоговая сложность алгоритма — [math] O(n) [/math]. Преподсчет [math] D [/math] можно выполнить динамически за [math] O(n^2) [/math].

Разбиения на множества

Разбиение на [math] k [/math] подмножеств

Рассмотрим множество первых [math] n [/math] натуральных чисел: [math] N_n = \{1, 2, \ldots, n\} [/math]. Необходимо построить его разбиение на [math] k [/math] непустых подмножеств [math] \{B_1, B_2, \ldots, B_k\} [/math] с равным распределением вероятности.

Будем строить разбиение таким образом, чтобы в результате подмножества [math] \{B_1, B_2, \ldots, B_k\} [/math] оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых [math]i, j \mid 1 \leqslant i \lt j \leqslant k [/math] наименьший элемент [math] B_i [/math] был меньше наименьшего элемента [math] B_j [/math]). Для этого будем по очереди добавлять каждое число от [math] n [/math] до [math] 1 [/math] в одно из подмножеств и для каждого из подмножеств начиная с [math] B_n [/math] и заканчивая [math] B_1 [/math] будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным).

На каждом шаге префиксом считаем текущее разбиение. Оно характеризуется двумя значениями: [math] l [/math] — число добавленных элементов и [math] m [/math] — число подмножеств для которых определен последний элемент. Заметим, что количество разбиений на подмножества с заданным префиксом равно числу способов разбить еще не добавленные элементы на еще не законченные подмножества так, чтобы они оказались лексикографически упорядочены, то есть равно числу разбиений [math] n-l [/math] элементов на [math] k-m [/math] непустых подмножеств, что равно [math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} [/math] (числу Стирлинга второго рода). Таким образом из префикса [math] P [/math] мы можем получить следующий префикс [math] P' [/math] двумя способами:

  • Добавить текущий элемент ([math] n-l [/math]) в одно из [math] k-m [/math] незаконченных подмножеств. В таком случае число обьектов с префиксом [math] P' [/math] будет равно [math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} [/math] .
  • Сделать текущий элемент последним в подмножестве [math] B_{k-m} [/math] . В таком случае это подмножество станет законченым, следовательно число обьектов с префиксом [math] P' [/math] будет равно [math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} [/math].

Таким образом на каждом шаге интервал случайных чисел [math] [0, s] [/math] (где [math] s = [/math][math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} [/math]) , будет разбиваться на два диапазона размерами [math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} [/math] и [math] (k-m)\cdot\genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} [/math]. Если случайно сгенерированное число попадет в первый диапазон, то сделаем [math] n-l [/math] последним элементом в подмножестве [math] B_{k-m} [/math] . Иначе добавим [math] n-l [/math] в случайно выбранное из незаконченных подмножеств ([math] \{B_1, B_2, \ldots, B_{k-m}\} [/math]).

int[] randomSetPartition(n: int k: int):  // [math] n [/math] — количество элементов в множестве, [math] k [/math] — число подмножеств на которые нужно разбить исходное множество. 
  l = 0
  m = 0
  downto i = n to 1                               
    s = stirling(n - l, k - m)  // [math] stirling(a, b) [/math] — функция возвращающая число Стирлинга второго рода для заданных аргументов. 
    r = random(1, s)
     if stirling(n - l - 1, k - m - 1) [math] \geqslant [/math] r
       result[i] = k - m  // [math] result[i] [/math] — номер подмножества в котором находится элемент [math] i [/math]. 
       l = l + 1
       m = m + 1
     else
       p = random(1, k - m)  // Случайным образом выбираем номер одного из незаконченных подмножеств. 
       result[i] = p
       l = l + 1
  return result

Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона, а всего шагов — [math] n [/math] то итоговая сложность алгоритма — [math] O(n) [/math] . Сложность преподсчета чисел Стирлинга второго рода — [math] O(n^2) [/math] если преподсчитать их динамически.

Разбиение на случайное число подмножеств

Описаный алгоритм можно применить для получения разбиения множества на случайное число подмножеств. Для этого достаточно случайным образом выбрать число подмножеств из интевала [math] [1, n] [/math] , так чтобы вероятность получить число [math] k [/math] была пропорциональна числу способов разбить [math] n [/math] элементов на [math] k [/math] подмножеств (что равно [math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{k} [/math]).

Разделим интервал случайных чисел [math] [1, s] [/math] (где [math] s = [/math] [math] \sum\limits_{i=1}^{n}{\genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i}}[/math]) на [math] n [/math] диапазонов, так чтобы размер диапазона [math] d_i [/math] был равен[math] \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i} [/math]. С помощью функции для генерации случайного числа получим число [math] r [/math] в интервале [math] [1, s] [/math]. Возьмем [math] k [/math] такое, что [math] r \in d_k [/math] и построим случайное разбиение множества из [math] n [/math] элементов на [math] k [/math] подмножеств.

См. также

Источники информации

  • Комбинаторные алгоритмы: учебное пособие / Т. И. Федоряева. — Новосибирск: Новосибирский гос. ун-т, 2011. 118 с. — ISBN 978-5-4437-0019-9
  • Non-Uniform Random Variate Generation / Luc Devroye. — Springer, New York, NY, 1986. 843 c. — ISBN 978-1-4613-8645-2