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