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

Материал из Викиконспекты
Версия от 03:29, 26 октября 2011; Antonkov (обсуждение | вклад) (Перестановки)
Перейти к: навигация, поиск

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

Рассмотрим алгоритм получения 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

Сочетания

Размещения

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

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