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