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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Правильные скобочные последовательности)
 
(не показано 39 промежуточных версий 7 участников)
Строка 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> 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> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов одинаково и равно, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </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> 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> 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>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>
 
<tex>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>
  
(считается, что все значения <tex> D[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 = 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> если случайное число попало в первый или второй диапазон соответственно.
+
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <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''' randomBracketSequence(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
 
  '''string''' randomBracketSequence(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
Строка 57: Строка 75:
 
     s = D[n - l][b]  
 
     s = D[n - l][b]  
 
     r = random(1, s)
 
     r = random(1, s)
       '''if''' D[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> k </tex> подмножеств ====
Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, ..., n\} </tex>. Необходимо разбить его на <tex> k </tex> непустых подмножеств <tex> \{B_1, B_2, ..., B_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, ..., B_k\} </tex> оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых <tex>i, j| 1 \leqslant i < j \leqslant k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_i </tex>). Для этого будем по очереди добавлять каждое число от <tex> n </tex> до <tex> 1 </tex> в одно из подмножеств и для каждого из подмножеств начиная с <tex> B_n </tex> и заканчивая <tex> B_1 </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 dpi = "180">\lbrace{n-l\atop k-m}\rbrace</tex> (т.е [[Числа Стирлинга второго рода|числу Стирлинга второго рода]]). Таким образом из префикса <tex> P </tex> мы можем получить следующий префикс <tex> P' </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 dpi = "180">\lbrace{n-l-1\atop k-m}\rbrace</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 dpi = "180">\lbrace{n-l-1\atop k-m-1}\rbrace</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 dpi = "180">\lbrace{n-l\atop k-m}\rbrace</tex>) , будет разбиваться на два диапазона размерами <tex dpi = "180">\lbrace{n-l-1\atop k-m-1}\rbrace</tex> и <tex> (k-m)\cdot </tex><tex dpi = "180">\lbrace{n-l-1\atop k-m}\rbrace</tex>. Если случайно сгенерированное число попадет в первый диапазон, то сделаем <tex> n-l </tex> последним элементом в подмножестве <tex> B_{k-m} </tex> . Иначе добавим <tex> n-l </tex> в случайно выбранное из незаконченных подмножеств (<tex> \{B_1, B_2, ..., B_{k-m}\} </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>
 
  '''int[]''' randomSetPartition(n: '''int''' k: '''int'''): <font color = green> // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. </font>
Строка 84: Строка 103:
 
   m = 0
 
   m = 0
 
   '''downto''' i = n '''to''' 1                               
 
   '''downto''' i = n '''to''' 1                               
     s = stirling(n - l, k - m) <font color = green> // <tex> stirling(a, b) </tex> - функция возвращающая число Стирлинга второго рода для заданных аргументов. </font>
+
     s = stirling(n - l, k - m) <font color = green> // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. </font>
 
     r = random(1, s)
 
     r = random(1, s)
       '''if''' stirling(n - l - 1, k - m - 1) >= r
+
       '''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>
+
         result[i] = k - m <font color = green> // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. </font>
 
         l = l + 1
 
         l = l + 1
 
         m = m + 1
 
         m = m + 1
Строка 96: Строка 115:
 
   '''return''' result
 
   '''return''' result
  
Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона а всего шагов {{---}} <tex> n </tex> то итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет чисел Стирлинга второго рода (если преподсчитать их динамически).
+
Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона, а всего шагов {{---}} <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 dpi = "180">\lbrace{n\atop k}\rbrace</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_{i=0}^n \left\{{n\atop i}\right\}</tex>) на <tex> n </tex> диапазонов, так чтобы размер диапазона <tex> d_i </tex> был равен <tex dpi = "180"> \lbrace{n\atop i}\rbrace </tex>. С помощью функции для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex> и выберем количество подмножеств <tex> k </tex> соответствующее диапазону отрезка в которм находится полученное число и по выбранному <tex> k </tex> получим случайное разбиение множества размера <tex> n </tex> на <tex> 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> подмножеств.
  
 
== См. также ==
 
== См. также ==
Строка 108: Строка 127:
  
 
== Источники информации ==
 
== Источники информации ==
*Комбинаторные алгоритмы: учебное пособие / Т. И. Федоряева. - Новосибирск: Новосибирский гос. ун-т, 2011. 118 с. - ISBN 978-5-4437-0019-9
+
*Комбинаторные алгоритмы: учебное пособие / Т. И. Федоряева. {{---}} Новосибирск: Новосибирский гос. ун-т, 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
+
*Non-Uniform Random Variate Generation / Luc Devroye. {{---}} Springer, New York, NY, 1986. 843 c. {{---}} ISBN 978-1-4613-8645-2
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Текущая версия на 19:47, 18 декабря 2018

Задача:
Необходимо сгенерировать случайный комбинаторный объект размера [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