Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 7
Текст из файла (страница 7)
В разделе 1.2.10 мы рассматривали задачу о числе локальных максимумов перестановки, если читать ее справа налево. Иными словами, требовалось подсчитать количество элементов, каждый из которых балыке любого из следующих после него. (Например, правостороиние максимумы в (1) — это 3, 7, 8 и 9.) Оно равно количеству индексов 7', таких, что Ь имеет максимальное значение и — у. Так как Ь, будет равно и — 1 с вероятностью 1/и и (независимо) Ь будет равно и — 2 с вероятностью 1/(п — 1) и т. д,, из рассмотрения инверсий ясно, что среднее число правосторонних максимумов равно 1423 3214 3241 Рис. 1. Усеченный октвэдр, нв катаром показана изменение числа инверсий, когда меняются местами двв соседних элемента перестановки. 1 1 1 -+ — + .
+ =Нв. и и — 1 1 Аналогичным способом легко получить и соответствующую производягцую функцию. Ясно, что если поменять местами соседние элементы перестановки, то общее числа инверсий увеличится нли уменьшится на единицу. На рис. 1 показаны 24 перестановки множества (1, 2,3,4); линиями соединены перестановки, отличающиеся одна от другой положением двух соседних элементов; двигаясь вдоль линии вниз, мы увеличиваем число инверсий на единицу. Следовательио, число инверсий в перестановке и равно длине нисходящего пути из 1224 и гг на рис.
1; все такие пути должны иметь одинаковую длину. Заметим, что эту диаграмму можно рассматривать как трехмерное твердое тело — "усеченный октвэдр", имеющий 6 шестиугольных и 6 квадратных граней, Это один из классических правильных многогранников, которые исследовал еще Архпмед (см. упр, 10). Не следует путать "инверсии" перестановок (1птегэгапэ ог а регпшсаггоп) с обрвпгнм44н перестановками ((пвегэе о1 а регшцсасгап).
Вспомним, что перестановку можно записывать в виде двух строк: о! ггз аэ Обратной называется перестановка а', аз аз...а'„, которая получается, если в (4) поменять лгестами строки, а затем упорядочить столбцы в порядке возрастания по верхним элементам: п~ аа пэ ... а„ 1 2 3 ... и (5) Например, обратной к перестановке 591826473 будет перестановка 359716842, так как 5 7 5918264731 1'123456789"1 123456789/ 1359716842(' Можно дать другое определение обратной перестановки: а' = й тогда н только тогда, когда аэ — — .1 Понятие обратной перестановки впервые ввел Х. А. Роте (Н.
А. После) (в Яапил)ипй согпбшасолэсЬ-апа1убэсЛег АЫимиПппйеп. е61гес1 Ьу К. Г. Ишаев(гпгй. 2 (Ье1рхщ, 1800). 263-305). Он заметил интереснзю связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько инверсий, сколько исходная. Роте дал не самое простое доказательство этого факта, но оно поучителыю и притом довольно красиво. Построим таблицу размером и х и, наподобие шахматной доски, в которой точки стоят в 1'-й клетке Ьй строки, если а~ = у. После этого расставим крестики во всех клетках, снизу от которых (в том же столбце) и справа (в той же строке) есть точки.
Например, для 5918 26473 диаграмма будет выглядеть следующим образом: Количество крестиков равно числу инверсий, так как нетрудно видеть, что 51 равно числу крестиков в ~-и столбце. Если мы теперь транспонируем диаграмму (поменяв ролями строки и столбцы), то получим диаграмму для обратной по отношению к нсходпой перестановки; значит, число крестиков (чпсло инверсий) одинаково в обоих случаях. Роте испол зовал данный факт для доказательства того„что детерминант матрицгэ не меняется при транспонировании, Для анализа некоторых алгоритмов сортировки необходимо знать число перестановок и элементов, содержащих ровно Ь инверсий.
Обозначим это число через 1„(Й); в табл. 1 приведено несколько первых значений данной функции. Из таблицы инверсий Ь~ Ьэ...Ь„ясно, что У„(0) = 1, 1„(Ц = и — 1 и что выполняется свойство симметрии: 7„((",) — Ь) = 7„(Ь). (6) Далее, так как значения Ьь можно выбирать независимо одно от другого, нетрудно видеть. что производящая функция С„(л) = 1„(0) + 1„(1)х + Хэ(2)хэ + Таблица 1 ПЕРЕСТАНОВКА С х ИНВЕРСИЯМИ удовлетворяет соотношению О„(х) = (1+ х+ ".
+ г" ')сХ„с(х); следовательно, она имеет довольно простой вид, как показано О. Родригесом (О, Вобпйнш) (Х с(е Мас)ь 4 (1839), 236 — 240): (1 + э + + х" ') ... (1 + х)(1) = (1 — х") ... (1 — х~)(1 — х)/(1 — х)". (8) С помощью этой производящей функции можно легко продолжить табл. 1 и убедиться, что числа, расположенные под ступенчатой линией в таблице, удовлетворяют соотношению Х„(я) ж Х„(/с — 1) + Х„ с(/с), где и < и. (9) (Для чисел, находящяхся над ступенчатой линией, это соотношение ие выполняется.) Более сложные рассуждения (см. упр. 14) показывают, что на самом деле справедливы формулы Х„(2) = ~", ) — 1, п>2; Х„(3)= ~ ) — ~ ), п>3; ( ~п+ 3) ~п+ 2) Общая формула для Х„()с) содержит около 1.6Л слагаемых: и+)с-2 и+)с-3 и+(с-6 п+й-8 и+)с-ис-1 и+й-и.-у-1 где их = (3хе — Х)/2 — так называемое мпентагонэльное число".
Разделив С„(в) на ис, получим производящую функцию рм(э) распределения вероятностей числа инверсий в случайной перестановке и элементов. Она равна произведению 9 (л) = Хсс(х)/сс(х) ° ° - Ь (х) где Ьа(з) = (1+ д + + за ')/й — производящая функция равномерного распредьлепня случайной величины, принимающей целые неотрицательные значензш, гееныпне Ь. Отсюда' шеап(у„) = шеап(Ьь) + шеап(Ьу) + . + 1 о + — +" + 2 наг(д„) = наг(Рм) + ьаг(Рь ) + ° + шеап(Ьа) и — 1 п(п — 1) 2 4 наг(Ьн) пз — 1 п(2п+ о)(п — 1) (12) 1 о + — +".+ 4 Таким образом, среднее число инверсий довольно велико — около -'пз; стандартное отклонение также весьма велико — около Ьп~ь з.
б Б качестве интересного завершения данной темы рассмотрим одно замечательное открытие. принадлежащее П. А. Мак-Магону (Р. А. МасМайоп) (Ашег. Р. МайЬ. 35 (1913), 281 — 322). Определим ииь)екс перестановки оь и ... а„как сумму всех у'. таких, что ау > оуаь, 1 < Р с и. Например, индекс перестановки 591826473равен 2+ 4+ 6+8 = 20. Индекс случайно совпал с числом инверсий. Если составить список всех приведенных ниже 24 перестановок множества (1,2,3,4), то получится, что число перестановок, имеющих данный нядекс Ь, равно числу переспшовок, имеющих й пиверспРР.
Количество инверсий Количество инверсий Индекс Индекс 3 4 5 5 6 На первый взгляд, этот факт может показаться почти очевидным, однако после некоторых размышлений он начинает казаться чуть ли не мистическим. и не видно никакого простого прямого его доказательства. Мак-Магон нашел следующее остроумное косвенное доказательство. Пусть шь((аз аз...о„) — индекс перестановки аь оз...
ан и соотнетствуюгцая производящая функция есть О ( ) ~~, ньюаьаа,.а Р Здесь и далее шеаи(у) охьь аннет среднее значение случайной недичи ни у, а наг(у) — дне нерсиьо неличном у. — Хгрььн. аерае. Перестановка 1234 1 2 4)3 1 3)2 4 1 3 4(2 1 4(2 3 1 4(3!2 2)1 3 4 2)1 4)3 2 3(1 4 2 3 4(1 2 4(1 3 2 4)3(1 Перестановка 3)1 2 4 3(1 412 3(2(1 4 3(2 4(1 34,'1 2 3 4,'2(1 4(1 2 3 4)1 3(2 4(2(1 3 4)2 3(1 4)3)1 2 4)3)2(1 где сумма в (14) берется по всем перестановкам множества (1, 2,...,и), Требуется доказать, что Н„(т) = б„(х). Для этого определим взаимно однозначное соответствие между и-мерными строками (умят,..., д„) неотрицательных целых чисел, с одной стороны, и упорядоченными парами ц-мерных строк ((амат,...,а„), (рс,рз,...,р„)), с другой стороны.
где ас аз... а„— суть перестановка множества индексов (1, 2„ и) и р, > рз » р„> О. Это соответствие будет удовлетворять условию 9с+йа+".+с?,=шс)(асах а )+(рс+рз+"-+р,). (15) Производящая функция 2 хм ьме"'+т", где сумма берется по всем и-мерным строкам неотрицатс чьных целых чисел (дс, дт,....д„), равна С,с„(г) = 1/(1 — з)"; а производящая функция 2 тж+г'з "'+~", где сумма берется по всем и-мерным строкам целых чисел (рмра,,р„), таких, что рс > р„» - р„> О, равна Р„(з) = 1/(1 — л)(1 — х~)... (1 — х"), (16) как показано в упр.
15. Существование взаимно однозначного соответствия, которое удовлетворяет условию (15) и которое мы собираемся установить, доказывает равенство С/н(в) = Нн(з)Р„(л), т. е. (17) Н (х) = (4 (а)/Р (з). Но С„1„(г)/Р„(х) и есть 6„(г), как следует из (8). Требуемое соответствие определяется с помощью простой процедуры сортировки. Любая и-мгрная строка (йс,9т,...,Фн) может быть устойчиво реорганизована в поРЯдке невозРастаниЯ йю > д„, » . ° д,„, где ас ат...а„-- пеРестановка, такаи, что 9,, = 9„,~, и подРазУмевает а < а м Установим (Рс,Рм...,Р,,) = (д„.д„,...,с?,„) и затем для 1 < / < и вычтем 1 из каждого р„..., р д;ся таких /и которые соответствуют ау > ау„.с. По-прежнему рс > рт » р„, поскольку р обязательно превышает рзьм если только а > а ьь. Полученная в результате пара ((амат,...,а„),(рс,рм...,р„)) удовлетворяет условию (15), поскольку суммарное уменыпение элементов р равно Гпд(ас аз...
а„). Например, если и = 9 и (дм...,дд) = (3,1,4,1,5,9,2,6,5), то получим ас ...ач = 685931724 и (рм...,рэ) =- (5,2,2,2,2,2,1,1.1). Несложно вернуться к (щ, сст,..., д„), когда заданы ас аз... а„и (рс, рз,..., рн) (см, уир. 17). Итак„желаемое соответствие установлено, теорема Мак-Магона об индексах доказана, Д. Фиата (П. Гома) и М. П. Шуценберже (М. Р. 8сЫсвепЬегйет) отысюли неожиданное расширение теоремы Мак-Магона через 65 лет после его первой публикации. с!исто перестановок и элементов, которые имеют к инверсий и индекс 1, равно числу перестшювок, которые имеют ! ннверсси1 и пндекс к. Фактически Фоата н Шупенберже нашли простое однозначное соответствие между перестановками первого и вторсзго типов (см. упр.
25). УПРАЖНЕНИЯ 1. [10) Какова таблица инверсий лля перестановки 271845956? Какой перестановке соответствует таблица инверсий 5 О 1 2 1 2 О О? 2. [Мйй[ Классическая задача Иосифа формулируется следующим образом (см. также упр. 1.3.2-22): и рабов вначале стоят по кругу; после того как пмто раба казнят, круг смыкается, затем опять казнят гп-го раба и так до тех пор, пока всех рабсш не постигнет эта печальная участь. Таким образом, порядок, в котором рабы подвергаются наказанию, представляет собой перестановку множества (1,2,..., и). Например, еглн и = 8 и ги = 4, порядок будет иметь вид 54 61 3 872 (первым казнили 5-го раба и т.
д.); таблица инверсий для этой перестановки имеет вид 363100 10. Найдите простое рекуррентное соотношение для элементов 6| Ьз... Ь„таблицы инверсий в общей задаче Иосифа для и рабов, если каждого пмто раба казнят. 3. [18[ Пусть перестановке а~ аз, а соответствует таблица инверсий 6~ 6з .. Ь„. Какой перестановке а~ дз... О„соответствует таблица инверсий (и — 1 — 6))(п — 2 — Ьз) . (Π— Ьь)? 4. [80[ Придумайте пригодный для компьютерной реализации алгоритм, который по данной таблице инверсий 6| Ьз... Ь„, удовлетворяющей условиям (3), строил бм соответствуюп~ю перестановку а~ аэ... а .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
