394
правки
Изменения
→Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту
== Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта ] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов плюс 1(нумерацию ведём с 1).Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины i совпадает , а i+1 элемент лексикографически меньше i+1-го в данном объекте(i=0..n-1).
Следующий алгоритм вычисляет эту сумму
numOfObject=1 ''// numOfObject {{---}} искомый номер комбинаторного объекта
Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом.
Приведем примеры способов получения номеров некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по данному объекту.
== Перестановки ==
