Изменения

Перейти к: навигация, поиск

Получение объекта по номеру

57 байт убрано, 07:35, 30 октября 2011
Нет описания правки
== Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке ==
Получим элементы объекта по порядку: сначала определим какой элемент будет стоять на 1-м месте, 2-м и т.д. Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов элемента, который может стоять на (i+1)-ой позиции, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на (i+1)-ом месте. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции).
<code>
''//В начале каждого шага numOfObject {{---}} номер комбинаторного объекта среди объектов с заданным префиксом. ''
'''for''' i = 1 '''to''' n '''do''' ''//n {{---}} количество элементов в комбинаторном объекте''
'''then''' ans[i]=j ''//поставим на i-e место текущий элемент, т.к. еще не все объекты с этим префиксом - меньше''
перейти к выбору следующего элемента
</code>
Несложно понять, что корректность алгоритма следует из его построения.
Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов нахождения количества некоторых из [[Комбинаторные объекты|комбинаторных объектов]].
== Битовые вектора ==
Для некоторых комбинаторных объектов, например битовых векторов, можно привести явную [[Математический анализ:Отображения|биекцию]] из множества номеров в множество объектов.
В данном случае битовым вектором для номера n - будет являться его двоичное представление, которое можно получить гораздо легче,
чем генерировать объект общим алгоритмом. Если не учитовать особенности представления натуральных числе в памяти компьютера, то битовый вектор можно получить из числа за <tex>O(log{n}) </tex>, простым переводом десятичного числа n в двоичную систему счисления.
88
правок

Навигация