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

Определение

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

Пример

Возьмем перестановки из 3-х элементов в лексикографическом порядке, найдем перестановку под номером 4:

123 132 213 231 312 321

Искомая перестановка: 231.

Алгоритм

Пусть [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].

Алгоритм нахождение перестановки по номеру

Возьмем к примеру нахождение перестановки по номеру. Сначала определяем первую цифру перестановки, деля номер на (N-1)! и прибавляя 1, затем вторую, деля остаток от предыдущего деления на (N-2)!, и т.д.

Пример нахождения перестановки по номеру

Возьмем номер перестановки из 4 элементов: 13. Определим первую цифру перестановки, разделим нацело номер на (4-1)! и прибавим 1: [math]x_1[/math] = 13 div (3!) + 1 = 3. Остаток от деления: 1. Аналогично найдем 2-й элемент: [math]x_2[/math] = 1 div (2!) + 1 = 1. Остаток от деления: 1. 3-й элемент: [math]x_3[/math] = 1 div (1!)+1 = 1. Но т.к. число 1 уже использовалось в перестановке, возьмем следующий в лексикографическом порядке элемент, не используемый ранее, 2, следовательно [math]x_3[/math] = 2. 4-ый элемент получается исключением [math]x_4[/math] = 4. Получаем перстановку: 3124.

Ссылки

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