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

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

Получаем элементы объекта по порядку: сначала определим какой элемент будет стоять на первом месте, потом на втором, и так далее. Считаем, что мы нашли первые [math]i[/math] элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером [math]i+1[/math], посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на месте с номером [math]i+1[/math]. Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции.

• В начале каждого шага numOfObject — номер комбинаторного объекта среди объектов с заданным префиксом.

• n — количество мест в комбинаторном объекте (например, битовый вектор длины [math]n[/math])

• k — количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора [math]k=2[/math] : возможны только 0 и 1. Все элементы занумерованы в лексикографическом порядке, начиная с 1.

for i = 1 to n do                      
  for j = 1 to k do                      
    if j-ый элемент можно поставить на i-e место {
      if numOfObject > (количество комбинаторных обектов с данным префиксом) {
         numOfObject -= (количество комбинаторных обектов с данным префиксом)
      } else {
         ans[i] = j        
         break
      }
    }

Несложно понять, что корректность алгоритма следует из его построения. Сложность алгоритма — [math]O(nk) [/math]. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Хотя основную сложность при построении алгоритмов генерации комбинаторных объектов составляет именно вычисление количества комбинаторных объектов с заданным префиксом. Приведем примеры способов получения некоторых из комбинаторных объектов по номеру.

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

Рассмотрим алгоритм получения [math]i[/math]-ой в лексикографическом порядке перестановки размера [math]n[/math]. Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество перестановок не зависит от префикса) то есть можем просто посчитать "количество диапозонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за [math]O(1) [/math]:

• n! — количество перестановок размера [math]n[/math]

• permutation[n] — искомая перестановка

• was[n] — использовали ли мы уже эту цифру в перестановке

На [math]i[/math]-ом шаге:

• alreadyWas — сколько цифр уже полностью заняты перестановками с меньшим номером

• мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером alreadyWas + 1 среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра j

for i = 1 to n do {                               
  alreadyWas = (numOfPermutation - 1) div (n-i)!      
  numOfPermutation = ((numOfPermutation - 1) mod (n-i)! ) + 1  
  ans[i] = j (посчитаем за O(n))
  теперь j-ый элемент занят (находится в нашем префиксе)
}

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

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

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

• bitvector[n] — искомый битовый вектор

• 2^n — [math]2^{n}[/math] количество битовых векторов длины [math]n[/math]

for i = 1 to n do                                         
 if numOfObject > 2^(n-i) {
    numOfObject -= 2^(n-i)
    bitvector[i] = 1
 } else {
    bitvector[i] = 0        
 }

Данный алгоритм работает за [math]O(n)[/math], так как в случае битовых векторов [math]k[/math] не зависит от [math]n[/math].

См. также

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