Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      31 May 2001  22:49:08
 To : Alex Bachin
 Subject : Hомер перестановки
 -------------------------------------------------------------------------------- 
 
 
 Replying to a message of Alex Bachin to All:
 
  AB> есть некоторая перестановка чисел из множества.
  AB> (очевидно, количество этих перестановок N! - факториал)
  AB> Как бы так задать нумерацию этих перестановок,
  AB> чтобы для данной перестановки, быстро определить ее 
  AB> порядковый номер, и, что главнее, чтобы для кажодго 
  AB> номера быстро определить перестановку,
 
 Д Fido-style Netmail Area (2:5015/48.6) ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД NETMAIL Д
  From : Max Alekseyev                       2:5015/48.6     Sat 15 Feb 97 22:52 
  To   : Mark Nalbandyan                     2:464/58.1                          
  Subj : Как перенумеровать перестановки?                                        
 ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
 Hi, Mark !
 
 Friday February 14 1997 22:23, Mark Nalbandyan wrote to Max Alekseyev:
 
  MA>> 1) Сначала построим для перестановки т.н. таблицу инверсий :
  MA>> a_i = количеству чисел в перестановке стоящих перед i и больших i.
  MA>> 2) Hабору чисел (a_1,a_2,...,a_(n-1)) дадим номер
  MA>> a_1*(n-1)! + a_2*(n-2)! + ... + a_(n-1)*1! + 1
 
  MN>  Замечательно! Признавайся - сам придумал или где-то вычитал,
  MN> и если второе, то ГДЕ?
 
     Про таблицу инверсий и много всего другого можно прочитать, например, в
 Р. Стенли   Перечислительная комбинаторика, М. "Мир", 1990
 
  MN>  А всё же, что ты скажешь насчёт обратной задачи (получение перестановки
  MN> по её номеру без перебора всех предыдущих перестановок)?
 
     Все с точностью до наоборот :
 1) Строим по номеру k таблицу инверсий :
 s_1 = k-1   ("1" вычитаем, т.к. нумерация ведется с 1)
 
 a_i = [s_i/(n-i)!],        ([x] - целая часть x)
 s_(i+1) = s_i-a_i*(n-i)!,    i=1,2,...,n-1
 
 По этим формулам получаем таблицу инверсий (a_1,a_2,...,a_(n-1),0)
 
 2) Теперь построим собственно перестановку :
 Будем ставить числа n,n-1,...,1 на такие места, чтобы число инверсий для каждого
 i было в точности a_i.
 Пример для таблицы инверсий (1,5,2,0,4,2,0,1,0) :
 9
 98
 798
 7968
 79685
 479685
 4739685
 47396285
 417396285
 Итак, получили перестановку (4,1,7,3,9,6,2,8,5).
 
 Regards,
         Max
 ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
 
 Regards,      ш.ш
         Max    ~
 
 --- OS/2 Uptime:  1d 10h 15m 52s 203ms
  * Origin: Стая любит пить, стая любит жрать. (2:5015/60)
 
 

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

 Тема:    Автор:    Дата:  
 Hомер перестановки   Alex Bachin   30 May 2001 16:58:24 
 Hомер перестановки   Evgenij Masherov   30 May 2001 20:15:55 
 Hомер перестановки   Max Alekseyev   31 May 2001 22:49:08 
 Re: Hомер перестановки   Ihor Bobak   01 Jun 2001 11:54:09 
Архивное /ru.algorithms/18133b16ca7d.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional