Изменения
Нет описания правки
== Описание алгоритма ==
Получим элементы объекта по порядку: сначала определим какой элемент будет стоять на 1-м первом месте, 2-м втором и т.дтак далее. Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов элемента, который может стоять на (i+1)-ой позиции, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на (i+1)-ом месте. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции).
''В начале каждого шага numOfObject {{---}} номер комбинаторного объекта среди объектов с заданным префиксом. ''
== Перестановки ==
Рассмотрим алгоритм получения i-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера n.
Заметим, что всем префиксом на каждом шаге будет соответствовать диапазон номеров одинакового размера, (т.к. так как количество перестановок не зависит от префикса) т.е. то есть можем просто посчитать "количество диапозонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
<tex>P_{n} </tex> ''{{---}} количество перестановок размера n
alreadyWas ''{{---}} сколько цифр уже полностью заняты перестановками с меньшим номером''
''мы должны поставить ту цифру, которая еще полностью не занята, т.е. то есть alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j''
'''for''' i = 1 '''to''' n '''do'''
alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex>
