Изменения
Нет описания правки
== Описание алгоритма ==
Пусть <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> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> {{- --}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{--- }} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
*Любой комбинаторный объеут имеет пустой перфикс, следовательно <tex> S(\varnothing)=C(n) </tex>. Вероятность получить любой префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(P)\over{S(\varnothing)} </tex>, что равно <tex> S(P)\over{C(n)} </tex>.
*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> S(P)\over{C(n)} </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 dpi = "180">\lbrace{n-l\atop k-m}\rbrace</tex> (т.е [[Числа Стирлинга второго рода|числу Стирлинга второго рода]]). Таким образом из префикса <tex> P </tex> мы можем получить следующий префикс <tex> P' </tex> двумя способами:
*Добавить текущий элемент (<tex> n-l </tex>) в одно из <tex> k-m </tex> незаконченных подмножеств. В таком случае число обьектов с префиксом <tex> P' </tex> будет равно <tex dpi = "180">\lbrace{n-l-1\atop k-m}\rbrace</tex> .
*Сделать текущий элемент последним в подмножестве <tex> B_{k-m} </tex> . В таком случае это подмножество станет законченым, следовательно число обьектов с префиксом <tex> P' </tex> будет равно <tex dpi = "180">\lbrace{n-l-1\atop k-m-1}\rbrace</tex>.
Таким образом на каждом шаге интервал случайных чисел <tex> [0, s] </tex> (где <tex> s = </tex><tex dpi = "180">\lbrace{n-l\atop k-m}\rbrace</tex>) , будет разбиваться на два диапазона размерами <tex dpi = "180">\lbrace{n-l-1\atop k-m-1}\rbrace</tex> и <tex> (k-m)\cdot </tex><tex dpi = "180">\lbrace{n-l-1\atop k-m}\rbrace</tex>. Если случайно сгенерированное число попадет в первый диапазон, то сделаем <tex> n-l </tex> последним элементом в подмножестве <tex> B_{k-m} </tex> . Иначе добавим <tex> n-l </tex> в случайно выбранное из незаконченных подмножеств (<tex> \{B_1, B_2, ...\ldots, B_{k-m}\} </tex>).
'''int[]''' randomSetPartition(n: '''int''' k: '''int'''): <font color = green> // <tex> n </tex> {{---}} количество элементов в множестве, <tex> k </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. </font>
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) >= r
result[i] = k - m <font color = green> // <tex> result[i] </tex> {{- --}} номер подмножества в котором находится элемент <tex> i </tex>. </font>
l = l + 1
m = m + 1
