54
правки
Изменения
Добавлено описание алгоритма получение номера по разбиению на слагаемые
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.
== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного разбиение на слагаемые числа <tex>n</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически и будем строить его.
*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
*<tex>\mathtt{part[1..N]}</tex> {{---}} данное разбиение
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.
Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> по убыванию <tex>j</tex>.
Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex>, таких разбиений <tex>\mathtt{d[i - j][j]}</tex>, либо не содержать, таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>.
Получаем рекуррентное соотношение для подсчёта d:
<p>
<tex dpi = "145">d[i][j] =
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + dp[i - j][j], & i > j \end{array} \right.
</tex>
</p>
'''int''' part2num(part: '''list<int>'''):
numOfPart = 0
'''for''' i = 1 '''to''' N <font color=green>// <tex>n</tex> {{---}} число, которое было разбито на слагаемые </font>
'''for''' j = last '''to''' part[i] - 1 <font color=green>// перебираем все элементы, лексикографически меньше нашего, но больше или равны предыдущего</font>
numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
sum += part[i] <font color=green>// увеличиваем уже поставленную сумму</font>
last = part[i] <font color=green>// обновляем последний поставленный элемент </font>
'''return''' numOfPart <font color=green>// возвращаем ответ</font>
Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.
== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
