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