74
правки
Изменения
→Разбиения на множества
Описаный алгоритм можно применить для получения разбиения множество на случайное число подмножеств. Для этого достаточно случайным образом выбрать число подмножеств из интевала <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_{i=0}^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> n </tex> на <tex> k </tex>подмножеств.
