74
правки
Изменения
Нет описания правки
Будем строить префикс следующим образом: на каждом шаге интервал случайных чисел <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
'''for''' i = 1 '''to''' n
s = number[n - l][b]
*Сделать текущий элемент последним в подмножестве <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, ..., B_{k-m}\} </tex>).
'''int[]''' randomSetPartition(n: '''int''' k: '''int'''): <font color = green> // <tex> n </tex> {{---}} количество элементов в множестве, <tex> n </tex> {{---}} число подмножеств на которые нужно разбить исходное множество. </font>
l = 0
m = 0
'''for''' 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
'''else'''
p = random(1, k - m) <font color = green> // Случайным образом выбираем номер одного из незаконченных подмножеств. </font>
result[i] = p
l = l + 1
'''return''' result
Так как на каждом шаге интервал случайных чисел разделяется только на на два диапазона а всего шагов {{---}} <tex> n </tex> то итоговая сложность алгоритма {{---}} <tex> O(n) + O(n^2) </tex> на преподсчет чисел Стирлинга второго рода(если предпосчитать их динамически).
