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

Материал из Викиконспекты
Перейти к: навигация, поиск

Перестановки

Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки.

 [math]f[n]=n![/math]
 [math]ans[n][/math]                                                    //искомая перестановка
 [math]was[n][/math]                                                    //использовали ли мы уже эту цифру в переставновке
 for [math] i = 1 [/math] to [math] n [/math] do              //n-это количество цифр в перестановке
  [math] alreadyWas = (numOfPermutation-1) div f[n-i]  [/math] 
  [math] numOfPermutation = (numOfPermutation-1) mod f[n-i]  [/math] // сколько цифр уже полностью заняты предыдущими перестановками
  //сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. AlreadyWas+1
  for [math] j = 1 [/math] to [math] n [/math] do
    if [math] was[j] = false [/math] 
      then  [math] cntFree++ [/math]
    if [math] cntFree = AlreadyWas+1 [/math] 
     then  [math] ans[i] = j [/math]
           [math] was[j] =w true [/math]


Сочетания

Размещения

Битовые вектора

Скобочные последовательности