74
правки
Изменения
→Разбиения на множества
Будем строить разбиение таким образом, чтобы в результате подмножества <tex> \{B_1, B_2, ..., B_k\} </tex> оказались отсортированы в лексикографическом порядке (т.е. чтобы для любых <tex>i, j| 1 \leqslant i < j \leqslant k </tex> наименьший элемент <tex> B_i </tex> был меньше наименьшего элемента <tex> B_i </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, ..., B_{k-m}\} </tex>).
