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

Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту

Номер данного комбинаторного объекта равен количеству меньших в лексикографическом порядке комбинаторных объектов плюс 1(нумерацию ведём с 1).Все объекты меньшие нашего можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины i совпадает , а i+1 элемент лексикографически меньше i+1-го в данном объекте(i=0..n-1). Следующий алгоритм вычисляет эту сумму

 numOfObject=1                              // numOfObject — искомый номер комбинаторного объекта
 for  i = 1  to  n  do                      //перебираем элементы комбинаторного объекта
   for  j = 1  to  i-1  do                      //перебираем элементы которые в лексикографическом порядке меньше рассматриваемого
     if элемент j можно поставить на i-e место
       then numOfObject+=(коллличество комбинаторных объектов с данным префиксом)

т.е. он правильно находит номер данного объекта.

Несложно понять, что корректность алгоритма следует из его построения. Сложность алгоритма [math]O(n^{2}f(1..i)) [/math], где [math]f(1..i)[/math] - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов нахождения количества некоторых из комбинаторных объектов.

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

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

 [math]P_{n} [/math] — количество перестановок размера n
 permutation[n] — искомая перестановка
 was[n] — использовали ли мы уже эту цифру в перестановке
 for  i = 1  to  n  do                               //n - количество цифр в перестановке
   alreadyWas = (numOfPermutation-1) div [math]P_{n-i} [/math]      // сколько цифр уже полностью заняты перестановками с меньшим номером
   numOfPermutation = ((numOfPermutation-1) mod [math]P_{n-i} [/math]) + 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

Данный алгоритм работает за [math]O(n^2) [/math]. Мы можем посчитать [math]P_{n} [/math] за [math]O(n) [/math]. Асимптотику можно улучшить до [math]O(n log {n}) [/math], если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент множества за [math]O( log {n}) [/math]. Например декартово дерево по неявному ключу.

Размещения

Рассмотрим алгоритм получения i-го в лексикографическом порядке размещения [math] A^k_n [/math]

 [math]A^{k}_{n} [/math] — количество размещений из n по k
 placement[n] — искомое размещение
 was[n] — использовали ли мы уже эту цифру в размещении
 for  i = 1  to  k  do                               //k - количество цифр в размещении
   alreadyWas = (numOfPlacement-1) div [math] A^{k-i}_{n-i} [/math]      // сколько цифр уже полностью заняты размещениями с меньшим номером
   numOfPlacement = ((numOfPlacement-1) mod [math] A^{k-i}_{n-i} [/math]) + 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

Сложность алгоритма [math]O(nk) [/math].

Сочетания

Рассмотрим алгоритм получения i-го в лексикографическом порядке сочетания [math] С^k_n [/math]

 [math]С^{k}_{n} [/math] — количество сочетаний из n по k
 combination[n] — искомое сочетание
 was[n] — использовали ли мы уже эту цифру в сочетании
 for  i = 1  to  k  do                               //k - количество цифр в сочетании
   // вычтем те "группы" где, i-цифра меньше искомой
   numOfCombination = ((numOfCombination-1) mod [math] A^{k-i}_{n-i} [/math]) + 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

Сложность алгоритма [math]O(nk) [/math].

См. также

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