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

Материал из Викиконспекты
Перейти к: навигация, поиск

Определение

Получение объекта по номеру n- это нахождение объекта, который стоит n-ым в лексикографическом порядке.

Получение номера по объекту - это нахождение номера объекта, стоящего в лексикографическом порядке.

Алгоритм

Нахождение номера по объекту:

[math] n = \sum_{i=1}^l s_{a_i-1}[/math], где [math]s_m[/math] это кол-во возможных объектов длины [math]n-i+1[/math], начинающихся на элемент [math]m[/math], [math]l[/math] - длина данного объекта.

Нахождение объекта по номеру:

Пусть l - длина объекта. Идем по порядку по всем элементам объекта (i - позиция элемента в объекте). Каждый элемент p будет являться максимально возможным. Для p кол-во возможных объектов s, начинающихся на элемент p и имеющих длину l-i+1, не превосходит n. С каждым шагом n уменьшается на s.