лексикографический номер перестановки
Max Alekseyev
===cut===
Предположим, что все перестановки чисел 1,2,...,n лексикографически
упорядочены.
I. Как получить по перестановке ее номер?
Рассмотрим перестановку (p_1, p_2, ..., p_n).
1) Сначала построим для перестановки "лексикографическую" таблицу инверсий:
a_i = количеству индексов j таких, что n>=j>i и p_j<p_i.
Заметим, что a_n всегда равно 0.
2) Hабору чисел (a_1,a_2,...,a_{n-1}) дадим номер
a_1*(n-1)! + a_2*(n-2)! + ... + a_{n-1}*1! + 1
II. Как получить перестановку по ее лексикографическому номеру?
Все с точностью до наоборот:
1) Строим по номеру k таблицу инверсий:
s_1 = k-1 ("1" вычитаем, т.к. нумерация ведется с 1)
a_i = [s_i/(n-i)!], ([x] - целая часть x)
s_{i+1} = s_i mod (n-i)! = s_i-a_i*(n-i)! для i=1,2,...,n-1
По этим формулам получаем таблицу инверсий (a_1,a_2,...,a_{n-1},0)
2) Теперь построим собственно перестановку. Ее построение будем производить с
конца.
Предположим, что мы построили по "лексикографической" таблице инверсий
(a_{n+1-m},a_{n+2-m,...,a_{n-1},0) перестановку чисел 1,2,...,m и получили
(q_1,q_2,...,q_m).
Рассмотрим число t=a_{n-m}. Для i=1,2,...,m положим
q'_i = q_i, если q_i<=t;
q'_i = q_i + 1, если q_i>t.
Hетрудно проверить, что перестановка
(t+1,q'_1,q'_2,...,q'_m) соответствует "лексикографической" таблице инверсий
(a_{n-m},a_{n+1-m,...,a_{n-1},0)
Пример построения перестановки для таблицы инверсий (1,5,2,0,4,2,0,1,0):
1
21
132
3142
53142
164253
3175264
63185274
274196385
Итак, получили перестановку (2,7,4,1,9,6,3,8,5).
(c) 2001 by Max Alekseyev <re...@os2.ru>
2:5015/60@Fidonet
===cut===
Regards, ° °
Max ~
= = QU/2 playing: КОРОЛЬ и ШУТ - Прыгну Со Скалы