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 ш}\rbrace</tex>.
