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