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

Описание алгоритма

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

• [math]\mathtt{numOfObject}[/math] — искомый номер комбинаторного объекта,
• [math]\mathtt{a[1..n]}[/math] — данный комбинаторный обьект, состоящий из элементов множества [math]A[/math],
• [math]\mathtt{d[i][j]}[/math] — количество комбинаторных объектов с префиксом от [math]1[/math] до [math]i-1[/math] равным данному и с [math]i[/math]-м элементом равным [math]j[/math],

int object2num(a: list<A>):
  numOfObject = 0                          
  for i = 1 to n do                        // перебираем элементы комбинаторного объекта
    for j = [math]A_{min}[/math] to предшествующий элемент do               // перебираем элементы, которые в лексикографическом порядке меньше  рассматриваемого
      if элемент [math]j[/math] можно поставить на [math]i[/math]-e место
        numOfObject += d[i][j]
  return numOfObject

Сложность алгоритма — [math]O(nk) [/math], где [math]k[/math] {---} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора [math]k=2,[/math] поскольку возможны только [math]0[/math] и [math]1[/math]. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

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

Рассмотрим алгоритм получения номера [math]i[/math] в лексикографическом порядке данного битового вектора размера [math]n[/math]. Всего существует [math]2^n[/math] битовых векторов длины [math]n[/math]. На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия:

• [math]\mathtt{bitvector[1..n]}[/math] — данный вектор,
• [math]\mathtt{numOfBitvector}[/math] — искомый номер вектора,

int bitvector2num(bitvector: list<int>):
  numOfBitvector = 0
  for i = 1 to n do                                         
    if bitvector[i] == 1  
      numOfBitvector += pow(2, n - i)
  return numOfBitvector

Асимптотика алгоритма — [math]O(n) [/math].

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

Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера [math]n[/math],

• [math]\mathtt{a[1..n]}[/math] — данная перестановка,
• [math]\mathtt{P[1..n]}[/math] — количество перестановок данного размера,
• [math]\mathtt{was[1..n]}[/math] — использовали ли мы уже эту цифру в перестановке,

int permutation2num(a: list<int>):
  numOfPermutation = 0
  for i = 1 to n do                     // [math]n[/math] {---} количество элементов в перестановке 
    for j = 1  to a[i] - 1 do           // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на [math]i[/math]-м месте  
      if was[j] == false                // если элемент [math]j[/math] ранее не был использован 
        numOfPermutation += P[n - i]    // все перестановки с префиксом длиной [math]i-1[/math] равным нашему, и [math]i[/math]-й элемент у которых   
                                           меньше нашего в лексикографическом порядке, идут раньше данной перестановки                
    was[a[i]] = true                    // [math]i[/math]-й элемент использован            
  return numOfPermutation

Асимптотика алгоритма — [math]O(n ^ 2) [/math].

Сочетания

Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из [math]n[/math] по [math]k[/math]. Как известно, количество сочетаний из [math]n[/math] по [math]k[/math] обозначается как [math]\binom{n}{k}[/math]. Тогда число сочетаний, в которых на позиции [math]1[/math] стоит значение [math]val_1[/math], равно [math]$$\sum_{i=1}^{val_1-1} \binom{n-i}{k-1}$$[/math]; число сочетаний, в которых на позиции [math]2[/math] стоит значение [math]val_2[/math], равно [math]$$\sum_{i=val_1+1}^{val_2-1} \binom{n-i}{k-2}$$[/math]. Аналогично продолжаем по следующим позициям:

• [math]\mathtt{numOfChoose}[/math] — искомый номер сочетания,
• [math]\mathtt{C[n][k]}[/math] — количество сочетаний из [math]n[/math] по [math]k[/math], [math]\mathtt{C[n][0] = 1}[/math],
• [math]\mathtt{choose[1..K]}[/math] — данное сочетание, состоящее из [math]K[/math] чисел от [math]1[/math] до [math]N[/math], из технических соображений припишем ноль в начало сочетания: [math]\mathtt{choose[0] = 0}[/math],

// Нумерация сочетаний с [math]0[/math] 
int choose2num(choose: list<int>):
  numOfChoose = 0
  for i = 1 to K do                                         
    for  i = choose[i - 1] + 1 to choose[i] - 1 do
      numOfChoose += C[N - j][K - i]
  return numOfChoose

Асимптотика алгоритма — [math]O(K \cdot N) [/math].

См. также

• Получение объекта по номеру
• Получение номера правильной скобочной последовательности

Литература

• Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
• Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.