Получение объекта по номеру
Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке
for i = 1 to n do //n - количество элементов в комбинаторном объекте for j = 1 to n do //перебираем елементы в лексикографическом порядке if можем поставить на это место then if numOfObject > (количество комбинаторных обектов с данным префиксом) then numObject -= (количество комбинаторных обектов с данным префиксом) else then ans[i]=j //поставим на это место текущий элемент, т.к. еще не все объекты с этим префиксом - меньше перейти к выбору следующего элемента
Рассмотрим почему данный алгоритм корректен. Докажем по индукции, что мы верно выберем первые i-элементов объекта. Условимся, что нумерация обектов начинается с 1.
- База: i=0 - очевидно
- Докажем, что если первые i-элементов выбраны верно, то i+1 мы также выберем верно (на каждом шаге, numOfObject - номер комбинаторного объекта среди объектов с заданным префиксом).
- Переход: На i+1-ом шаге мы найдем, какой элемент должен быть i+1-ым для объекта с номером numOfOject, среди всех комбинаторных обектов, которые имеют префикс длины i - как у нас.
Рассмотрим искомый объект. Очевидно, что все объекты, у которых символ на
i+1 месте меньше чем у нас в лексикографическом порядке, будут идти раньше нас (префикс совпадает, а i+1 символ меньше), т.е. наш номер, по крайней мере больше, количества таких объектов. А те у которых больше будут идти после нас, т.е. даже номер найменьшего из них будет больше нашего. Тогда
(суммы всех комбинаторных объектов с ">=" префиксом) >= numOfObject > (суммы всех комбинаторных объектов с меньшим "<" префиксом)
т.е. в итоге из построения алгоритма мы поставим именно тот элемент, который нам нужен.
Далее продолжим искать среди объектов, которые имеют одинаковый префикс длины i+1, изменив номер на номер среди комбинаторных объектов с текущим префиксом.
Перестановки
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки размера n.
- количество перестановок размера n permutation[n] - искомая перестановка was[n] - использовали ли мы уже эту цифру в перестановке for i = 1 to n do //n - количество цифр в перестановке alreadyWas = (numOfPermutation-1) div // сколько цифр уже полностью заняты перестановками с меньшим номером numOfPermutation = ((numOfPermutation-1) mod ) + 1 //сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята for j = 1 to n do if was[j] = false then cntFree++ if cntFree = alreadyWas+1 then ans[i] = j was[j] = true
Данный алгоритм работает за
. Мы можем посчитать за . Асимптотику можно улучшить до , если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент множества за . Например декартово дерево по неявному ключу.Сочетания
Рассмотрим алгоритм получения i-го в лексикографическом порядке размещения
- количество размещений из n по k placement[n] - искомое размещение was[n] - использовали ли мы уже эту цифру в размещении for i = 1 to k do //k - количество цифр в размещении alreadyWas = (numOfPlacement-1) div // сколько цифр уже полностью заняты размещениями с меньшим номером numOfPlacement = ((numOfPlacement-1) mod ) + 1 //сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята for j = 1 to n do if was[j] = false then cntFree++ if cntFree = alreadyWas+1 then ans[i] = j was[j] = true
Сложность алгоритма
.