48
правок
Изменения
Нет описания правки
Получаем элементы объекта по порядку: сначала определим какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит на это место больше нельзя поставить никакой другой элемент.
*В начале каждого шага numOfObject {{---}} номер комбинаторного нужного объекта среди объектов с заданным префиксомтех, у которых префикс до i-го элемента лексикографически равен префиксу нашего объекта.
*n {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>)
'''for''' i = 1 '''to''' n '''do'''
'''for''' j = 1 '''to''' k '''do'''
'''if''' j-ый элемент можно поставить на i-e место '''{''' '''if''' numOfObject >= (количество комбинаторных обектов объектов с данным префиксомobject[1..i-1] и элементом j на месте i) '''{''' numOfObject -= (количество комбинаторных обектов объектов с данным префиксомobject[1..i-1] и элементом j на месте i) '''} else {''' object[i] = j выходим из цикла поиска элемента на i-е место '''}''' '''}'''
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
== Перестановки ==
Рассмотрим алгоритм получения <tex>ik</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
*n! k {{---}} количество перестановок размера <tex>n</tex>номер искомой последовательности
*permutation[n] ! {{---}} искомая перестановкаколичество перестановок размера <tex>n</tex>.
*permutation[n] {{---}} искомая перестановка. *was[n] {{---}} использовали ли мы уже эту цифру в перестановке.
На <tex>i</tex>-ом шаге:
*alreadyWas {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером alreadyWas + 1 среди . Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра j.
На <tex>kj</tex>-ом шаге:
*curFree {{---}} если элемент с номером <tex>kj</tex> свободен, то он имеет номер curFree среди всех свободных элементов с 1 по <tex>kj</tex> '''for''' i = 1 '''to''' n '''do''' '''{''' alreadyWas = numOfPermutation k div (n-i)! numOfPermutation k = numOfPermutation k mod (n-i)!
curFree = 0
'''for''' k j = 1 '''to''' n '''do''' '''if''' was[kj] == false '''{'''
curFree++
'''if''' curFree == alreadyWas + 1 '''{''' j = k выходим из цикла поиска j '''}''' '''}''' permutation[i] = j was[j] = true '''}'''
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все n! за <tex>O(n) </tex>. Асимптотику можно улучшить
до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-ый элемент множества и удалять элемент
'''for''' i = 1 '''to''' n '''do'''
'''if''' numOfBitvector >= pow(2^, (n-i) '''{''') numOfBitvector -= pow(2^, (n-i)) bitvector[i] = 1 '''} else {''' bitvector[i] = 0 '''}'''
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>.
== См. также ==
*[[Получение номера по объекту|Получение номера по объекту]]
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31- ISBN 5-94774-010-9
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
