88
правок
Изменения
→Перестановки
was[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'''
'''then ''' ans[i] = j
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>. Например декартово дерево по неявному ключу.
== Сочетания ==
