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

Определение

Получение объекта по номеру 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] - длина данного объекта.

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

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

Примеры

Алгоритм вычисления по перестановке ее номера. Нам задана произвольная перестановка из [math]N[/math] чисел. Пусть [math]x[/math] - ее первое число. Тогда все перестановки с первыми числами от 1 до [math]x-1[/math] находятся перед нашей. Их количество [math]s[/math] равно [math](x-1)·(N-1)![/math]. Осталось узнать номер перестановки из [math]N-1[/math] числа, получающейся из нашей выбрасыванием числа [math]x[/math], и прибавить этот номер к [math]s[/math]

Алгоритм получения перестановки по ее номеру реализуется аналогично: сначала определяем первую цифру перестановки, деля номер на [math](N-1)![/math] и прибавляя 1, затем вторую, деля остаток от предыдущего деления на [math](N-2)![/math], и т.д.

Ссылки

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