1632
правки
Изменения
м
'''int''' part2num(part: '''list<int>'''): numOfPart = 0, last = 0, sum = 0 '''for''' i = 1 '''to''' N <font color=green>// <tex>N</tex> {{---}} число, которое было разбито на слагаемые </font> part.size '''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>
rollbackEdits.php mass rollback
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
*<tex>\mathtt{P[1..(n]- i)!}</tex> {{---}} количество перестановок данного размера<tex>(n - i)</tex>,
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,
'''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font>
'''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>
numOfPermutation += P[(n - i] )! <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>
<font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font>
was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font>
== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера , в лексикографическом порядке данного разбиение , по данному разбиению на слагаемые числа <tex>nN</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически , и будем строить его.
*<tex>\mathtt{numOfPart}</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>).
Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:
Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.
Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.
