1632
правки
Изменения
м
== Описание алгоритма ==
Пусть <tex> B = \{b_1, b_2 ..., b_k\} </tex> - множество различных элементов, которые могут находиться в данном комбинаторном объекте.
=== Доказательство корректности =={{Лемма|statement=Докажем по индукции, что вероятность Вероятность получить любой перфикс в процессе работы алгоритма некоторый префикс <tex> P </tex> равна <tex> C(n)\overdfrac{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(\varnothingP)\over}{S(P\varnothing)} </tex>, что равно <tex> C(n)\overdfrac{S(P)}{C(n)} </tex>.*'''Переход:''' Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> C(n)\overdfrac{S(P)}{C(n)} </tex>*Тогда вероятность . Вероятность получить из <tex> P </tex> любой некоторый префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> C\dfrac{S(P')}{S(nP)} </tex> , следовательно вероятность получить префикс <tex> P' </tex> равна <tex> \overdfrac{S(P)}{C(n)} </tex><tex>\cdot</tex><tex> \dfrac{S(P')\over}{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> \overdfrac{S1}{C(P'n)} </tex>.}} == Примеры решения задач ==Рассмотрим примеры использования данного алгоритма для генерации различных типов комбинаторных объектов.
Рассмотрим "полуправильные" скобочные последовательности т.е. такие что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты. Такую последовтеьность можно охарактеризовать двумя числами: Научимся считать <tex> D[l][b] </tex> {{---}} число последовательностей длины <tex> l </tex> — длина скобочной последовательности и баланса <tex> b </tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок). Заметим что любой префикс правильной скобочной последовательности является "полупраильной" скобочной последовательностьюЕсли <tex> l = 0 </tex>, то ответ понятен сразу: <tex> D[0][0] = 1 </tex>, и что для любого префикса все остальные <tex> P D[0][b] = 0 </tex> длины . Пусть теперь <tex> l > 0 </tex> число различных ПСП длины , тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> n '(' </tex> равно числу "полуправильных" скобочных последовательностей длины , то до этого символа мы находились в состоянии <tex> n(l-l 1,b-1) </tex>. Если он был равен <tex>')'</tex> с таким же балансом как у , то предыдущим было состояние <tex> P (l-1,b+1)</tex>.Таким образом, получаем формулу:
Научимся считать <tex> number(l, b) </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>). Если <tex> D[l = 0 </tex>, то ответ понятен сразу: <tex> number[0][0b] = 1 </tex>, все остальные <tex> number[0]D[b] = 0 </tex>. Пусть теперь <tex> i > 0 </tex>, тогда переберём, чему мог быть равен последний символ этой последовательности. Если он был равен <tex> '(' </tex>, то до этого символа мы находились в состоянии <tex> (l-1,][b-1) </tex>. Если он был равен <tex>')'</tex>, то предыдущим было состояние <tex>(] + D[l-1,][b+1)]</tex>. Таким образом, получаем формулу:
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = number[n - l][b] </tex>) , будет разбиваться на два диапазона размерами <tex> number[n - l - 1][b + 1] </tex> и <tex> number[n - l - 1][b - 1] </tex> , и к префиксу будет прибавляться <tex>'('</tex> или <tex>')'</tex> если случайное число попало в первый или второй диапазон соответственно. '''string''' randomObjectrandomBracketSequence(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font> b = 0 l = 0
rollbackEdits.php mass rollback
{{Задача
|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'''): <font color = green> // <tex> n </tex> {{---}} размер комбинторного объекта, <tex> k </tex> {{---}} число различных элемнтов.</font>
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
=== Битовые вектора ===Рассмотрим алгоритм получения случайного [[Комбинаторные объекты#Битовые вектора|битового вектора]]. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов длины <tex> n </tex> одинаково и равно<tex> 2^{n-l} </tex>, следовательно на каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>
'''vector<int>''' randomBitVector(n: '''int'''): <font color = green> // <tex> n </tex> {{---}} размер битового вектора.</font>
Сложность алгоритма {{---}} <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> — баланс {{---}} разность между количеством открывающих и закрывающих скобок. Заметим что любой префикс правильной скобочной последовательности является полуправильной скобочной последовательностью, и что для любого префикса <tex> P </tex> длины <tex> l </tex> число различных правильных скобочных последовательностей длины <tex> n </tex> равно числу полуправильных скобочных последовательностей длины <tex> n-l </tex> с таким же балансом как у <tex> P </tex>.
(считается, что все значения <tex>numberD[l][b] = number[l-1][</tex> при отрицательном <tex>b-1] + number[l-1][b+1]</tex>равны нулю).
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (считаетсягде <tex> s = D[n-l][b] </tex>) , что все значения будет разбиваться на два диапазона размерами <tex> numberD[n-l-1][b+1] </tex> при отрицательном и <tex>jD[n-l-1][b-1] </tex> равны нулю). Этот преподсчет можно выполнить за , и к префиксу будет прибавляться <tex>O'(n^2'</tex> или <tex>')'</tex>если случайное число попало в первый или второй диапазон соответственно.
'''for''' i = 1 '''to''' n
s = numberD[n - l][b]
r = random(1, s)
'''if''' numberD[n - l - 1][b + 1] <tex> \geqslant </tex>= r
l = l + 1
b = b + 1
'''return''' result
Итоговая сложность алгоритма {{---}} <tex> O(n) </tex>. Преподсчет <tex> D </tex> можно выполнить динамически за <tex> O(n^2) </tex>. === Разбиения на множества ======= Разбиение на <tex> k </tex> подмножеств ====Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, \ldots, n\} </tex>. Необходимо построить его [[Комбинаторные объекты#Разбиение на подмножества|разбиение на <tex> k </tex> непустых подмножеств]] <tex> \{B_1, B_2, \ldots, B_k\} </tex> с равным распределением вероятности. Будем строить разбиение таким образом, чтобы в результате подмножества <tex> \{B_1, B_2, \ldots, B_k\} </tex> оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых <tex>i, j \mid 1 \leqslant i < j \leqslant k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_j </tex>). Для этого будем по очереди добавлять каждое число от <tex> n </tex> до <tex> 1 </tex> в одно из подмножеств и для каждого из подмножеств начиная с <tex> B_n </tex> и заканчивая <tex> B_1 </tex> будем выбирать какой элемент будет добавлен в него последним(т.е. будет минимальным). На каждом шаге префиксом считаем текущее разбиение. Оно характеризуется двумя значениями: <tex> l </tex> — число добавленных элементов и <tex> m </tex> — число подмножеств для которых определен последний элемент. Заметим, что количество разбиений на подмножества с заданным префиксом равно числу способов разбить еще не добавленные элементы на еще не законченные подмножества так, чтобы они оказались лексикографически упорядочены, то есть равно числу разбиений <tex> n-l </tex> элементов на <tex> k-m </tex> непустых подмножеств, что равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} </tex> ([[Числа Стирлинга второго рода|числу Стирлинга второго рода]]). Таким образом из префикса <tex> P </tex> мы можем получить следующий префикс <tex> P' </tex> двумя способами: *Добавить текущий элемент (<tex> n-l </tex>) в одно из <tex> k-m </tex> незаконченных подмножеств. В таком случае число обьектов с префиксом <tex> P' </tex> будет равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} </tex> .*Сделать текущий элемент последним в подмножестве <tex> B_{k-m} </tex> . В таком случае это подмножество станет законченым, следовательно число обьектов с префиксом <tex> P' </tex> будет равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} </tex>.Таким образом на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = </tex><tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l}{k-m} </tex>) , будет разбиваться на два диапазона размерами <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m-1} </tex> и <tex> (k-m)\cdot\genfrac{\lbrace}{\rbrace}{0pt}{0}{n-l-1}{k-m} </tex>. Если случайно сгенерированное число попадет в первый диапазон, то сделаем <tex> n-l </tex> последним элементом в подмножестве <tex> B_{k-m} </tex> . Иначе добавим <tex> n-l </tex> в случайно выбранное из незаконченных подмножеств (<tex> \{B_1, B_2, \ldots, B_{k-m}\} </tex>). '''int[]''' randomSetPartition(n: '''int''' k: '''int'''): <font color = green> // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. </font> l = 0 m = 0 '''downto''' i = n '''to''' 1 s = stirling(n - l, k - m) <font color = green> // <tex> stirling(a, b) </tex> {{---}} функция возвращающая число Стирлинга второго рода для заданных аргументов. </font> r = random(1, s) '''if''' stirling(n - l - 1, k - m - 1) <tex> \geqslant </tex> r result[i] = k - m <font color = green> // <tex> result[i] </tex> {{---}} номер подмножества в котором находится элемент <tex> i </tex>. </font> l = l + 1 m = m + 1 '''else''' p = random(1, k - m) <font color = green> // Случайным образом выбираем номер одного из незаконченных подмножеств. </font> result[i] = p l = l + 1 '''return''' result Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона, а всего шагов {{---}} <tex> n </tex> то итоговая сложность алгоритма {{---}} <tex> O(n) </tex> . Сложность преподсчета чисел Стирлинга второго рода {{---}} <tex> O(n^2) </tex> если преподсчитать их [[Динамическое программирование | динамически]]. ==== Разбиение на случайное число подмножеств ====Описаный алгоритм можно применить для получения разбиения множества на случайное число подмножеств. Для этого достаточно случайным образом выбрать число подмножеств из интевала <tex> [1, n] </tex> , так чтобы вероятность получить число <tex> k </tex> была пропорциональна числу способов разбить <tex> n </tex> элементов на преподсчет<tex> k </tex> подмножеств (что равно <tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{k} </tex>). Разделим интервал случайных чисел <tex> [1, s] </tex> (где <tex> s = </tex> <tex dpi="180"> \sum\limits_{i=1}^{n}{\genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i}}</tex>) на <tex> n </tex> диапазонов, так чтобы размер диапазона <tex> d_i </tex> был равен<tex> \genfrac{\lbrace}{\rbrace}{0pt}{0}{n}{i} </tex>. С помощью функции для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex>. Возьмем <tex> k </tex> такое, что <tex> r \in d_k </tex> и построим случайное разбиение множества из <tex> n </tex> элементов на <tex> k </tex> подмножеств. == См.также ==*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Метод генерации случайной перестановки]]*[[Методы генерации случайного сочетания|Методы генерации случайного сочетания]]
== Разбиения на множества Источники информации ===== Разбиение на <tex> k <*Комбинаторные алгоритмы: учебное пособие /tex> подмножеств ===Рассмотрим множество первых <tex> n </tex> натуральных чисел: <tex> N_n = \{1, 2, Т.И.Федоряева., n\{{---}} </tex>Новосибирск: Новосибирский гос. Необходимо разбить его на <tex> k </tex> непустых подмножеств <tex> \{B_1, B_2ун-т, 2011.118 с.., B_k\{{---}} <ISBN 978-5-4437-0019-9*Non-Uniform Random Variate Generation /tex> с равным распределением вероятностиLuc Devroye.Будем строить разбиение таким образом{{---}} Springer, чтобы в результате подмножества <tex> \{B_1New York, B_2NY, 1986.843 c.., B_k\{{---}} </tex> оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых <tex> ISBN 978-1 <= i < j <= k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_i </tex>).-4613-8645-2[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]