88
правок
Изменения
Нет описания правки
== Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке Описание алгоритма ==
Получим элементы объекта по порядку: сначала определим какой элемент будет стоять на 1-м месте, 2-м и т.д. Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов элемента, который может стоять на (i+1)-ой позиции, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на (i+1)-ом месте. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции).
'''if''' элемент j можно поставить на i-e место
'''then if''' numOfObject > (количество комбинаторных обектов с данным префиксом)'''
'''then''' numOfObject -= (количество комбинаторных обектов с данным префиксом)
'''else'''
'''then''' ans[i]=j ''//поставим на i-e место текущий элемент, т.к. еще не все объекты с этим префиксом - меньше''
перейти к выбору следующего элемента
Несложно понять, что корректность алгоритма следует из его построения.
