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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 17: Строка 17:
 
                     перейти к выбору следующего элемента
 
                     перейти к выбору следующего элемента
 
Несложно понять, что корректность алгоритма следует из его построения.
 
Несложно понять, что корректность алгоритма следует из его построения.
Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
+
Сложность алгоритма <tex>O(nkf(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
  
 
== Перестановки ==
 
== Перестановки ==
 
Рассмотрим алгоритм получения i-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера n.
 
Рассмотрим алгоритм получения i-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера n.
 
Заметим, что всем префиксом на каждом шаге будет соответствовать диапазон номеров одинакового размера, (т.к. количество перестановок не зависит от префикса) т.е. можем просто посчитать "количество диапозонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
 
Заметим, что всем префиксом на каждом шаге будет соответствовать диапазон номеров одинакового размера, (т.к. количество перестановок не зависит от префикса) т.е. можем просто посчитать "количество диапозонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
  <tex>P_{n} </tex> ''{{---}} количество перестановок размера n
+
 
  permutation[n] ''{{---}} искомая перестановка''
+
<tex>P_{n} </tex> ''{{---}} количество перестановок размера n
  was[n] ''{{---}} использовали ли мы уже эту цифру в перестановке''
+
 
   '''for'''  i = 1  '''to'''  n  '''do'''                              ''//n - количество цифр в перестановке''
+
permutation[n] ''{{---}} искомая перестановка''
     alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex>      ''// сколько цифр уже полностью заняты перестановками с меньшим номером''
+
 
 +
was[n] ''{{---}} использовали ли мы уже эту цифру в перестановке''
 +
 
 +
На i-ом шаге:
 +
 
 +
alreadyWas ''{{---}} сколько цифр уже полностью заняты перестановками с меньшим номером''
 +
 
 +
''мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j''
 +
 
 +
   '''for'''  i = 1  '''to'''  n  '''do'''                               
 +
     alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex>       
 
     numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1   
 
     numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1   
    ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j''
 
 
     ans[i] = j (посчитаем за <tex>O(n) </tex>)
 
     ans[i] = j (посчитаем за <tex>O(n) </tex>)
 
     теперь j-ый элемент занят (находится в нашем префиксе)
 
     теперь j-ый элемент занят (находится в нашем префиксе)
  
Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить  
+
Данный алгоритм работает за <tex>O(n^2) </tex> (n=k). Мы можем посчитать все <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить  
 
до <tex>O(n \log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент  
 
до <tex>O(n \log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент  
 
множества за <tex>O( \log {n}) </tex>. Например декартово дерево по неявному ключу.
 
множества за <tex>O( \log {n}) </tex>. Например декартово дерево по неявному ключу.

Версия 03:38, 1 ноября 2011

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

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

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

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

k — количество различных элементов, которые могут находиться в данном комбинаторном объекте (элемент лексикографически меньше другого, если номер элемента меньше номера другого) (например для битового вектора k=2 : возможны только 0 и 1)

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

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

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

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

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

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

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

На i-ом шаге:

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

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

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

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

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

Для некоторых комбинаторных объектов, например битовых векторов, можно привести явную биекцию из множества номеров в множество объектов. В данном случае битовым вектором для номера n — будет являться его двоичное представление, которое можно получить гораздо легче, чем генерировать объект общим алгоритмом. Если не учитовать особенности представления натуральных числе в памяти компьютера, то битовый вектор можно получить из числа за [math]O(\log{n}) [/math], где n — номер вектора (log n = длине битового вектора), простым переводом десятичного числа n в двоичную систему счисления.

См. также

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

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