Изменения
Нет описания правки
Заметим, что всем префиксом на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество перестановок не зависит от префикса) то есть можем просто посчитать "количество диапозонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
*'''f[n]!''' {{---}} количество перестановок размера <tex>n</tex>
*'''permutation[n]''' {{---}} искомая перестановка
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером '''alreadyWas''' + 1 среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра '''j'''
'''for''' i = 1 '''to''' n '''do''' '''{'''
alreadyWas = (numOfPermutation - 1) div f[(n-i] )! numOfPermutation = ((numOfPermutation - 1) mod f[(n-i])! ) + 1
ans[i] = j (посчитаем за O(n))
теперь j-ый элемент занят (находится в нашем префиксе)
'''}'''
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все '''f[n]!''' за <tex>O(n) </tex>. Асимптотику можно улучшить
до <tex>O(n \log {n}) </tex>, если использовать структуры данных, которые позволяют искать <tex>i</tex>-ый элемент множества и удалять элемент
множества за <tex>O( \log {n}) </tex>. Например декартово дерево по неявному ключу.
