Получение объекта по номеру — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перестановки)
(Перестановки)
Строка 7: Строка 7:
 
     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, которая еще не занята''
 
     '''for'''  j = 1  '''to'''  n  '''do'''
 
     '''for'''  j = 1  '''to'''  n  '''do'''
 
       '''if'''  was[j] = false   
 
       '''if'''  was[j] = false   
 
         '''then '''  cntFree++  
 
         '''then '''  cntFree++  
      '''if'''  cntFree = alreadyWas+1   
+
                  '''if'''  cntFree = alreadyWas+1   
        '''then '''  ans[i] = j  
+
                    '''then '''  ans[i] = j  
              was[j] = true
+
                                was[j] = true
  
 
== Сочетания ==
 
== Сочетания ==

Версия 03:38, 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

Сочетания

Размещения

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

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