Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 69
Текст из файла (страница 69)
'ь й / Число разбиений зп иа пе более чем и частей равно, таким образом, („,) /и! + О(т" з) при фиксированном и, как следует из упр. 5.1.1-1о. Это также асимптотическое число разбиений т = рз+ +р, когда части раз отчим — рз » р„> 0 (см, упр. 5.1.1 16). Таким образом, чи«за обратпых плоских разбиений асимптотически приближается к 7зз(„, ) /и(+ О(зп з), если имеется й! диаграмм данной формы из п ячеек. Из и. (а) это также есть („з)/Дйо +О(пз" 'з).
[Ззипйез т А!з!з!!ес! Маей, 50 (1971), 167-188, 259 — 279) 37. Плоское разбиение на прямоугольнике эквивалентно обратиому плоскому разбиению, так что длины уголков дают нам произволяпзую функцию 1/П;., П',(1 — озфз ) на прямоугольнике г х с. Если положим г,с -ь ао, то получим ответ в очень элегантном виде: 1/(1 — о)(1 — е~)~(1 — оь) .... [Вывод принадлежит Мак-Мазону и оцубликован в Рй!!озорй!зв! Тгапзась!олз 211 (1912), 75-110, 345-373, ио там он имел гораздо более сложную форму. Первым простое доказательство нашел Леопард Карлиц (Ьеопагз! Сэг!Мз), Асьа Апзйтейса 13 (1967), 29 — 47.] 38, (а) Вероятиость равна 1/и при й = ! = 1; в противном случае, применяя ицзбзкцию по й+ 1, получим пР(1 зз (зо), 7) + пР(1, .У зз (/о)) (зйоь + з!азо)/(пзйоь ° ° з! ь зь з!о!о ° ° о(озз з) и з!зоьа з(зоь + Зозо (Ь) Суммированиепо всем 1и э дает и '(1+з(зь')...
(1+з!! ' ззь) (1+з1,з')... (1+з(„'ь,з ), что, как легко видеть, равно /(Т '1 ((и, Ь)))//(Т). (с) Суммирование по всем угловым ячейкам дает 1, поскольку каждый путь заканчивается в какой-либо угловой ячейке. Таким образом, 2 /(Т 'з ((а,Ь))) = /(Т), а это доказывает теорему Н, если применить индукцию по и.
Более того, если разместить и в угловой ячейке в конце случайного пути и повторить процесс иа оставшихся и — 1 ячейках, получится каждый вариант диаграммы с вероятностью 1/7(Т). (Адгепсев !л Магй. 31 (1979), 104-109.» 39. (а) !вум... !ггв будут иметь вид Ьу... Ь„, т. е. будут представлять собой таблицу инверсий исходных перестановок Р1 у... Рг (см. раздел 5,1,1). (Ь) !,Ум . !учу — таблица инверсий с обратным знаком ( — Су)... (-С„) из упр. 5.1.1-7. (с) Это условие, очевидно, предусматривается на шаге РЗ, (д) (зз ) -+ ((у ), ( „')); (, ) -в (( ), (о „)), Этот пример показывает, что нельзя выполнять шаг РЗ в обратном направлении,не просмотрев массив Р. (е) (!) Следующий алгоритм корректен, но ие очевиден.
ьв1. (Цикл по (1, у).» Выполнить вуаги О2 и !43 для каждой ячейки (у,у) массива в лексикогрж»уическом порядке (т. е, сверху вниз и слева направо в каждой строке), затем прекратить выполнение процедуры. ь)2. »Изменение с).» Найти "первого кацлидата» (г, в) по правилу, которое будет изло- жено ниже. Затем присвоить Оцьг,у +- Оу» — 1 для у < Ь < в. 433. »Восстановление Р в (1„у),» Присвоить А' +- Р„. Затем выполиять следующие операции до тех пор, пока не будет выполнено условие (г, в) = (г, у').
Ясли Ры 0, > Р,, М присвоить Р„+- Ры и, и г +- г — 1; в противугом случае присвоя ь Р,. +- Рм, 0 и в+- в — 1. И, наконец, присвоить Рп в- К. $ На шаге ()2 ячейка (г,в) является кандидатом, если в > у и Яи < О, и у = ! — !дм. Пусть Т вЂ” ориентированное дерево, построеиное в соответствии с указанием. Один из основных инвариаитов алгоритма с! состоит в том, что на этом дереве будет существовать путь от (г, в) к (б У) в Т всякий раз, когда (г, в) является кандидатом иа шаге С)2.
Обратный путь к нему можно закодировать последовательностью букв О, Уд и В, означающих, что мы начали в ячейке (у, у), затем спустились (П) или поглли вправо (В ), или закончили (с!). Первый каидидат — лто олип из кандидатов, код которого в лексикографическом смысле стоит раньше других; интуитивно кажется, что ои должен быть крайним слева и снизу по отношению к "коикуреитам'! Например, кандидатами при (г, у) = (1, 1) в примере п.
(е) являются (3, 1), (4, 2), (2, 3), (2, 4) и (1, б). Им соответствуют коды ИХ), ИМЖуд, ВОШЗ, ИЗЖИЛА) и ВВКВЖ1; из иих первым будет (4, 2). Алгоритм Р представляет собой несколько упрощенную версию построения, описанного без доказательства в работе, опубликованной в журнале Функциональный аиллиз и его првложепия, 20, 3 (1992), 80-82.
Доказательство корректности этого построения отнюдь не очевидно и дава Ж.-К. Новелли (Л.-С. Иове!(!), И, Паком (1. РаЫ) и А. В. Стояиовским (А. У, Згоуавотэйу!) в ПЫс. Магй. ауд ТйеогеНсэу Сот р. Боб 1 (1997), ЬЗ-б7. 40. Эквивалентный процесс проанализирован в работе Н, Вгмц Зеугвсбгвй Гбг ИгабшсйшлуусбйейвгбеоПе плд кегяавдге Оеб!еге 38 (1981), 41-53. 41.
(Решение предчожеио Р. У. Флойдом (В. %. Г!оуд),) Операции удаления-встааки фактически перемещает только а,, В процессе ее выполнения иезатроиугые элементы сохраняют гюрядок. Таким образом, если перестановку я можно рассортировать при помоуци Ь операций удаления-вставки, то она имеет возрастаюпгую подпоследовательность длиной и — 7г, и наоборот. Следовательно, Йз(к) = и — (длина самой длинной возрастающей подпоследовательностн в я) = и + (длина строки 1 в теореме А).
М. Л. Фредмвл (М. ! . Ггебшап) доказал, что наименьшее количество сравнений, необходимое для вычисления этой длины., равно и!6 и — и !8 !8 и+ О(п) (!1мсгеге Маей. 11 (1975), 29-35). 42. Постройте мультигрвф с вершинами (Ол, 1с, 1я,, пщ ил, (и+ 1) ь ) и ребрами )гл— ()г+ 1)ь при 0 < к < и, включите также ребра Ол — 7л, 7ь — 1щ 1я — 2ь, 2л — 4ь, 4л — ощ Ьл — Зь, Зл — бл, бь — Зщ которы» соответствуют "узам" в ЬоЬе(!а уегэепэ, К каждой вершине подходит в точности два ребра, так что связанные компоненты являются циклами: (Ол1с 7ь бя Зя4ь 2л Зс о»6ьЗь 7л)(1л 2ь)(4л Ьь). Некоторая операция перебрасывания изменяет количество циклов на -1, 0 или +1.
Таким образом, нам понадобится, по крайней мере, пять операций для того, чтобы прийти к восьми циклам (Ол 1ь)(1л 2ь)... (7я 8ь). (Л. Кесес!об!и, П. Банко!1, Еессше Хо!щ !л Сощр. Яс!. 807 (1994), 307-325.] Первая операция должна разорвать узы бь — Зщ поскольку мы не достигнем никакого нового цикла после разрыва двух уз, которые имеют одинаковую ориентацию свева направо в линейном представлении. В результате после одной операции появляется пять вариантов, а именно — дг уауз уэ 94 уэ у~, ут у~ уэдэуэдзув, уг у~уэуеуэ уэ уэ, уг й уэдэуэуэуз л кляли и и ялл л и и дэдэ Уэ 94 дэ д, дэч еще четырех операций достаточно для того, чтобы рассортировать все, лля ля кроме второй из них.
Супшствует 2 . 7! = 645 120 разных вариантов компоновки д~ . Уг и 179 904 из них находятся на расстоянии < 5 от порядка в молекуле ДНК табака. (Эффективный алгоритм поиска наилучшего способа сортировки любой перестановки со знаком посредством реверсирования был изложен в работе Б. Наппепйа!Ы, Р. Ретхпег, ХАСМ 46 (1999), 1 — 27, а усовершенствован — в работе Кар1ап, БЬаш!г, Тацвл, ЯО!1А 8 (1997)., 344-ЗЬЦ 43.
Обозначим компоновку наподобие дг д~ дтдэдэдэде посредством перестановки со знаком я и 7124536. Если существует отрицательный элемент, например я, но отсутствует л' — 1, одна операции перебрасывания создаст двойной цикл (()г — 1)я кь). Аналогично, если имеется !г, но отсутствует я'+ 1, единственная операция перебрасывания сформирует ()гк (я+1) ь).
И если все операции такого вида удаляют все отрицательные элементы, то единственное перебрасывание формирует два двойных цикла. Если отсутствуют отрицательные элементы, а перестановка не рассортирована, некоторые из перебрасываний будут сохранять количество циклов. Следовательно, за < и перебрасываний можно выполнить сортировку, если данная перестановка имеет отрицательный элемент; в противном случае необходимое количество перебрасыванкй составит < и + 1, Если и четное, перестановка п(п — 1) ... 1 требует и+ 1 перебрасываний, поскольку в ней будет один цикл после первого перебрасывания. Если и > 3 нечетно, то, рассуждая аналогично, прихолим к выводу, что для перестановки 21 3 и (и-1) ... 4 потребуется и+ 1 операция.
44. Пусть сэ — число циклов длиной 2я в мультиграфе из ответа к предыдущему упражнению. Верхняя граница для среднего значения сэ может быть найдена следующим образом. Общее число потенциальных 26-циклов равно 2" (и+ 1)к/(2)г), поскольку мы можем выбрать (и+1)к способами последовательность л различных ребер из (Оя — 1ь,..., пл— (и + 1)ь) и ориентировать нх 2" способами. Таким образом, каждый цикл будет подсчитал 2)г раз, включая и невозможные случаи наподобие (1я 2ь 2л Зь), (1я 2ь Зь 2л Зл 4ь) и (1я 2ь бя 7ь 4ь Зл 2я Зь бь ол). Если А < п, каждый возможный 2Й-цикл появляется точно в 2" "(и - !г)! перестановках со знаком.
Например, рассмотрим случай, когда я = Ь, РАЗДЕЛ 5.2 1. Да; ! и у могут изменяться в диапазоне 1 <,1' < ( < х в произвольном порядке. это позволяет выполнять подсчет параллельно с вводом данных. 2. Сортировка будет устойчива в том смысле, как определено в начале этой главы, поскольку алгоритм, по существу, вьпюлняет упорядочение в ленснкографическом порядкеразлнчающихсл пар ключей (Км 1), (Км 2),..., (Кл, Х). (Если представить себе, что к каждому ключу справа добавлен его адрес в файле, то равных ключей не будет, а значит, озртировка будет устойчива.) 3. Программа все-такн будет выполнять сортировку, но это будет неустойчивая сортировка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
