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