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