Изменения

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

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

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

Навигация