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

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

 for  i = 1  to  n  do                      //n - количество элементов в комбинаторном объекте
   for  j = 1  to  n  do                      //перебираем елементы в лексикографическом порядке
     if  можем поставить на это место
       then if numOfObject > (количество комбинаторных обектов с данным префиксом)
              then  numObject -= (количество комбинаторных обектов с данным префиксом)
            else
              then  ans[i]=j        //поставим на это место текущий элемент, т.к. еще не все объекты с этим префиксом - меньше
                    перейти к выбору следующего элемента

Рассмотрим почему данный алгоритм корректен. Докажем по индукции, что мы верно выберем первые i-элементов объекта. Условимся, что нумерация обектов начинается с 1.

База: i=0 - очевидно

Докажем, что если первые i-элементов выбраны верно, то i+1 мы также выберем верно (на каждом шаге, numOfObject - номер комбинаторного объекта среди объектов с заданным префиксом).

Переход: На i+1-ом шаге мы найдем, какой элемент должен быть i+1-ым для объекта с номером numOfOject, среди всех комбинаторных обектов, которые имеют префикс длины i - как у нас.
Рассмотрим искомый объект. Очевидно, что все объекты, у которых символ на

i+1 месте меньше чем у нас в лексикографическом порядке, будут идти раньше нас (префикс совпадает, а i+1 символ меньше), т.е. наш номер, по крайней мере больше, количества таких объектов. А те у которых больше будут идти после нас, т.е. даже номер найменьшего из них будет больше нашего. Тогда
(суммы всех комбинаторных объектов с ">=" префиксом) >= numOfObject > (суммы всех комбинаторных объектов с меньшим "<" префиксом)
т.е. в итоге из построения алгоритма мы поставим именно тот элемент, который нам нужен.
Далее продолжим искать среди объектов, которые имеют одинаковый префикс длины i+1, изменив номер на номер среди комбинаторных объектов с текущим префиксом.

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

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