Получение объекта по номеру — различия между версиями
Antonkov (обсуждение | вклад) (→Перестановки) |
Antonkov (обсуждение | вклад) (→Перестановки) |
||
| Строка 7: | Строка 7: | ||
alreadyWas = (numOfPermutation-1) div f[n-i] ''// сколько цифр уже полностью заняты перестановками с меньшим номером'' | alreadyWas = (numOfPermutation-1) div f[n-i] ''// сколько цифр уже полностью заняты перестановками с меньшим номером'' | ||
numOfPermutation = ((numOfPermutation-1) mod f[n-i]) + 1 | numOfPermutation = ((numOfPermutation-1) mod f[n-i]) + 1 | ||
| − | ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 | + | ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' |
'''for''' j = 1 '''to''' n '''do''' | '''for''' j = 1 '''to''' n '''do''' | ||
'''if''' was[j] = false | '''if''' was[j] = false | ||
'''then ''' cntFree++ | '''then ''' cntFree++ | ||
| − | + | '''if''' cntFree = alreadyWas+1 | |
| − | + | '''then ''' ans[i] = j | |
| − | + | was[j] = true | |
== Сочетания == | == Сочетания == | ||
Версия 03:38, 26 октября 2011
Перестановки
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки.
f[n]=n!
permutation[n] //искомая перестановка
was[n] //использовали ли мы уже эту цифру в перестановке
for i = 1 to n do //n - количество цифр в перестановке
alreadyWas = (numOfPermutation-1) div f[n-i] // сколько цифр уже полностью заняты перестановками с меньшим номером
numOfPermutation = ((numOfPermutation-1) mod f[n-i]) + 1
//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята
for j = 1 to n do
if was[j] = false
then cntFree++
if cntFree = alreadyWas+1
then ans[i] = j
was[j] = true
