29
правок
Изменения
Нет описания правки
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма.
'''function''' num2object(numOfObject: '''int''')
'''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)
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
*<tex>\mathtt{k }</tex> {{---}} номер искомой последовательности
*<tex>\mathtt{n! }</tex> {{---}} количество перестановок размера <tex>n</tex>.
*<tex>\mathtt{permutation[n] }</tex> {{---}} искомая перестановка.
*<tex>\mathtt{was[n] }</tex> {{---}} использовали ли мы уже эту цифру в перестановке.
На <tex>i</tex>-ом шаге:
*<tex>\mathtt{alreadyWas }</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером.
*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <tex>alreadyWas + 1</tex>. Среди цифр, которых еще нет в нашем префиксе, считаем, что это цифра <tex>j</tex>.
На <tex>j</tex>-ом шаге:
*<tex>\mathtt{curFree }</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1 </tex> по <tex>j</tex>
'''function''' num2permutation(k: '''int''')
'''for''' i = 1 '''to''' n '''do'''
'''return''' permutation
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>n! </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-ый й элемент множества и удалять элемент
множества за <tex>O( \log {n}) </tex>.
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:
*<tex>\mathtt{bitvector[n] }</tex> {{---}} искомый битовый вектор
*<tex>\mathtt{numOfBitvector }</tex> {{---}} номер искомого вектора среди всех битовых векторов
*<tex>\mathtt{pow(2, n) }</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex>
'''function''' num2bitvector(numOfBitvector: '''int''')
'''for''' i = 1 '''to''' n '''do'''
== См. также ==
*[[Получение номера по объекту|Получение номера по объекту]]
== Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
