|
|
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) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/18133b16ca7d.html, оценка из 5, голосов 10
|