Изменения

Получение номера по объекту

396 байт убрано, 06:28, 30 октября 2011

Нет описания правки

was[n] ''{{---}} использовали ли мы уже эту цифру в перестановке''

'''for''' i = 1 '''to''' n '''do''' ''//n - количество цифр в перестановке''

~~alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex> ''// сколько цифр уже полностью заняты перестановками с меньшим номером''~~

~~''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята''~~

'''for''' j = 1 '''to''' i-1 '''do'''

'''if''' was[j] = false

'''then ''' numOfPermutation+= <tex>P_{n-i} </tex>

Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить

394

правки