Изменения

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

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

1 байт убрано, 08:43, 28 ноября 2011
Описанте алгоритма
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте(<tex>i</tex> = 0..<tex>n-1</tex>).
Следующий алгоритм вычисляет эту сумму
numOfObject = 0 ''// numOfObject {{---}} искомый номер комбинаторного объекта
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы которые в лексикографическом порядке меньше рассматриваемого''
394
правки

Навигация