ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      06 Jun 2001  16:38:28
 To : All
 Subject : лексикографический номер перестановки
 -------------------------------------------------------------------------------- 
 

 
 ===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 <relf@os2.ru>
 2:5015/60@Fidonet
 ===cut===
 
 Regards,      ш.ш
         Max    ~
 =.= QU/2 playing: КОРОЛЬ и ШУТ - Прыгну Со Скалы
 --- OS/2 Uptime:  0d 17h 56m 46s 945ms
  * Origin: Мне не с кем выйти в логово врага. (2:5015/60)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор