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