74
правки
Изменения
Нет описания правки
(считается, что все значения <tex> D[l][b] </tex> при отрицательном <tex>j</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'''): <font color = green> // <tex> n </tex> {{---}} длина скобочной последовательности. </font>
Описаный алгоритм можно применить для получения разбиения множества на случайное число подмножеств. Для этого достаточно случайным образом выбрать число подмножеств из интевала <tex> [1, n] </tex> , так чтобы вероятность получить число <tex> k </tex> была пропорциональна числу способов разбить <tex> n </tex> элементов на <tex> k </tex> подмножеств (что равно <tex dpi = "180">\lbrace{n\atop k}\rbrace</tex>).
Разделим интервал случайных чисел <tex> [1, s] </tex> (где <tex> s = </tex> <tex dpi = "180"> \sum\limits_{i=1}^{n}\left\{{n\atop i}\right\}</tex>) на <tex> n </tex> диапазонов, так чтобы размер диапазона <tex> d_i </tex> был равен <tex dpi = "180"> \lbrace{n\atop i}\rbrace </tex>. С помощью функции для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex> и выберем количество подмножеств <tex> k </tex> соответствующее диапазону отрезка в которм находится полученное число и по выбранному <tex> k </tex> получим случайное разбиение множества размера <tex> n </tex> на <tex> k </tex> подмножеств.
== См. также ==
== Источники информации ==
*Комбинаторные алгоритмы: учебное пособие / Т. И. Федоряева. {{- --}} Новосибирск: Новосибирский гос. ун-т, 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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
