Изменения

Получаем элементы объекта по порядку: сначала определим какой элемент будет стоять на первом месте, потом на втором, и так далее. Считаем, что мы нашли первые <tex>i</tex> элементов объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени должен стоять на месте с номером <tex>i+1</tex>. Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции.

Несложно понять, что корректность алгоритма следует из его построения.Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Хотя основную сложность при построении алгоритмов генерации комбинаторных объектов составляет именно вычисление Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксомзачастую является задачей с достаточно большой вычислительной сложностью. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.

Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество перестановок не зависит от префикса) то есть можем просто посчитать "количество диапозоновдиапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>: