Получение объекта по номеру — различия между версиями
Antonkov (обсуждение | вклад) (→Перестановки) |
Antonkov (обсуждение | вклад) (→Перестановки) |
||
| Строка 2: | Строка 2: | ||
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки. | Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки. | ||
f[n]=n! | f[n]=n! | ||
| − | permutation[n] | + | permutation[n] ''//искомая перестановка'' |
| − | was[n] | + | was[n] ''//использовали ли мы уже эту цифру в перестановке'' |
| − | '''for''' i = 1 '''to''' n '''do''' | + | '''for''' i = 1 '''to''' n '''do''' ''//n - количество цифр в перестановке'' |
| − | 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''''' | ||
Версия 03:31, 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
