Викиконспекты - Вклад участника [ru]

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

2018-12-16T17:43:43Z

217.66.156.56: /* Разбиения на множества */

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''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>.
{{Определение
|definition='''Полуправильная скобочная последовательность''' (анлг. ''Semi-correct 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>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>

(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= 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> оказались отсортированы в '''лексикографическом порядке''' (англ. ''lexicographical order'') (т.е. чтобы для любых <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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T17:36:27Z

217.66.156.56:

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''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>.
{{Определение
|definition='''Полуправильная скобочная последовательность''' (анлг. ''Semi-correct 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>D[l][b] = D[l-1][b-1] + D[l-1][b+1]</tex>

(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= 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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T17:05:37Z

217.66.156.56: /* Примеры решения задач */

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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>.
}}

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

=== Битовые вектора ===
Рассмотрим алгоритм получения случайного [[Комбинаторные объекты#Битовые вектора|битового вектора]] (англ. ''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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''for''' i = 1 '''to''' n
r = random(0, 1)
v[i] = r
'''return''' prefix

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

=== Правильные скобочные последовательности ===
Рассмотрим алгоритм получения случайной [[Правильные скобочные последовательности|правильной скобочной последовательности]] (анлг. ''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> 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] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= 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> непустых подмножеств]] (анлг. ''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> будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным).

На каждом шаге префиксом считаем текущее разбиение. Оно характеризуется двумя значениями: <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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T16:55:12Z

217.66.156.56:

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''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>.
{{Определение
|definition='''Полуправильная скобочная последовательность''' {{---}} скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты.
}}
Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: <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] = D[l-1][b-1] + D[l-1][b+1]</tex>

(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= 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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T11:49:31Z

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

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

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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>.
}}

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

=== Битовые вектора ===
{{Определение
|definition='''[[Комбинаторные объекты#Битовые вектора|Битовые вектора]]''' (англ. ''Bit vectors'') {{---}} последовательность нулей и единиц заданной длины.
}}
Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''for''' i = 1 '''to''' n
r = random(0, 1)
v[i] = r
'''return''' prefix

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

=== Правильные скобочные последовательности ===
{{Определение
|definition ='''[[Правильные скобочные последовательности|Правильная скобочная последовательность]]''' (анлг. ''Correct Bracket Sequence'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:

*<tex>\varepsilon</tex> (пустая строка) есть правильная скобочная последовательность;
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
}}
Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная последовательность состоит из двух типов элементов: открывающей и закрывающей скобок, следовательно <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> 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] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= n </tex>. Преподсчет <tex> D </tex> можно выполнить динамически за <tex> O(n^2) </tex>.

=== Разбиения на множества ===
{{Определение
|definition=[[Комбинаторные объекты#Разбиение на подмножества|'''Разбиение множества''' <tex>X</tex> '''на подмножества''']] (англ. ''Partition of a set'') {{---}} семейство непустых множеств <tex>\{U_{\alpha}\},{\alpha \in A}</tex>, где <tex>A</tex> {{---}} некоторое множество индексов, если:
# <tex>U_{\alpha} \cap U_{\beta} = \emptyset</tex> для любых <tex>\alpha, \beta \in A</tex>, таких что <tex>\alpha \not= \beta</tex>;
# <tex>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T11:38:23Z

217.66.156.56:

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

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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>.
}}

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

=== Битовые вектора ===
{{Определение
|definition='''[[Комбинаторные объекты#Битовые вектора|Битовые вектора]]''' (англ. ''Bit vectors'') {{---}} последовательность нулей и единиц заданной длины.
}}
Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''for''' i = 1 '''to''' n
r = random(0, 1)
v[i] = r
'''return''' prefix

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

=== Правильные скобочные последовательности ===
{{Определение
|definition ='''[[Правильные скобочные последовательности|Правильная скобочная последовательность]]''' (анлг. ''Correct Bracket Sequences'') {{---}} частный случай скобочной последовательности, определяющийся следующими образами:

*<tex>\varepsilon</tex> (пустая строка) есть правильная скобочная последовательность;
*пусть <tex>S</tex> {{---}} правильная скобочная последовательность, тогда <tex>(S)</tex> есть правильная скобочная последовательность;
*пусть <tex>S1</tex>, <tex>S2</tex> {{---}} правильные скобочные последовательности, тогда <tex>S1S2</tex> есть правильная скобочная последовательность;
}}
Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная последовательность состоит из двух типов элементов: открывающей и закрывающей скобок, следовательно <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> 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] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= n </tex>. Преподсчет <tex> D </tex> можно выполнить динамически за <tex> O(n^2) </tex>.

=== Разбиения на множества ===
{{Определение
|definition=[[Комбинаторные объекты#Разбиение на подмножества|'''Разбиение множества''' <tex>X</tex> '''на подмножества''']] (англ. ''Partition of a set'') {{---}} семейство непустых множеств <tex>\{U_{\alpha}\},{\alpha \in A}</tex>, где <tex>A</tex> {{---}} некоторое множество индексов, если:
# <tex>U_{\alpha} \cap U_{\beta} = \emptyset</tex> для любых <tex>\alpha, \beta \in A</tex>, таких что <tex>\alpha \not= \beta</tex>;
# <tex>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T11:03:05Z

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

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''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>.
{{Определение
|definition='''Полуправильная скобочная последовательность''' {{---}} скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты.
}}
Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: <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] = D[l-1][b-1] + D[l-1][b+1]</tex>

(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b] </tex> известно для любых <tex> l, b \mid l <= n, b <= 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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-12-16T11:02:26Z

217.66.156.56:

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

Сложность алгоритма {{---}} <tex>O(nk) </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> с таким префиксом.
|proof=Докажем по [[Математическая индукция|индукции]]:

'''База:''' Заметим, что любой комбинаторный объект имеет пустой префикс (<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> 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'''): // <tex> n </tex> {{---}} размер битового вектора.
'''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>.
{{Определение
|definition='''Полуправильная скобочная последовательность''' {{---}} скобочная последовательность такая, что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты.
}}
Рассмотрим полуправильные скобочные последовательности. Такую последовтеьность можно охарактеризовать двумя числами: <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] = D[l-1][b-1] + D[l-1][b+1]</tex>

(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>b</tex> равны нулю). Этот преподсчет можно выполнить за <tex>O(n^2)</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'''): // <tex> n </tex> {{---}} длина скобочной последовательности. 
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] >= r
l = l + 1
b = b + 1
result = result + '('
'''else'''
l = l + 1
b = b - 1
result = result + ')'
'''return''' result

Сложность алгоритма {{---}} <tex> O(n) </tex> при условии что <tex> D[l][b]n </tex> известно для любых <tex> l, b \mid l <= n, b <= 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'''): // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. 
l = 0
m = 0
'''downto''' i = n '''to''' 1
s = stirling(n - l, k - m) // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. 
r = random(1, s)
'''if''' stirling(n - l - 1, k - m - 1) >= r
result[i] = k - m // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. 
l = l + 1
m = m + 1
'''else'''
p = random(1, k - m) // Случайным образом выбираем номер одного из незаконченных подмножеств. 
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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]