Д. Кнут - Искусство программирования том 1 (1119450), страница 48
Текст из файла (страница 48)
Чтобы ответить на,него, рассмотрим множество всех и! перестановок, представленных в канонической форме, и уберем скобки. Останется множество всех и! перестановок, расположенных в некотором порядке. Поэтому первоначальный вопрос будет эквивалентен следующему: "Сколько в среднем минимумов слева направо имеет перестановка из и элементов?". На последний вопрос мы уже ответили в разделе 1.2.10; это была величина (А + 1) из анализа алгоритма 1.2.10М, для которой найдены статистические характеристики ппп 1, аче Н„, шах и, меч ̈́— Н~~ ~. (21) (На самом деле мы искали среднее число максимумов справа налево, но очевидно, что это то же самое, что число минимумов слева направо.) Более того, мы, в сущности, доказали, что перестановка из п объектов имеет к минимумов слева направо с вероятностью [„"] /и!; следовательно, перестановка пз п объектов имеет к циклов с вероятностью [„]/и!. Можно также задать вопрос о среднем расстоянии между минимумами слева направо, которое эквивалентно средней длине цикла.
Согласно (21) общее число циклов во всех и! перестановках равно п! Н„, так как это п!, умноженное на среднее число циклов. Если выбрать один из этих циклов наугад, то чему будет равна его средняя длина? Представьте себе все п1 перестановок (1,2,...,п), записанных в циклической форме.
Сколько среди них будет трехэлементных циклов? Чтобы ответить на этот вопрос, выясним, сколько раз появляется конкретный трехэлементный цикл (хул). Очевидно, что он появляется ровно в (п — 3)! перестановках, так как это число способов, которыми можно переставить оставшиеся п — 3 элемента. Количество различных возможных трехэлементных циклов (х у г) равно п(п — 1)(и — 2)/3, поскольку х можно выбрать п способами, у — (и — 1) способами, а л — (и — 2) способами, и среди этих п(п — 1)(п — 2) вариантов каждый отличный от других трехэлементный цикл появляется в трех формах; (хул), (улх), (лху). Поэтому общее число трехэлементных циклов среди всех и! перестановок равно п(п — 1) х (и-2)/3, умноженному на (и — 3)), т.
е. и!/3. Аналогично общее число гл-элементных циклов равно и!/т, где 1 < т < и. (Это дает еще одно простое доказательство того факта, что общее число циклов равно и! Н„. Следовательно, как мы уже знаем, среднее число циклов в случайной перестановке равно Н„.) В упр. 17 показано, что средняя длина случайно выбранного цикла равна и/Н„, если считать, что все и! Н„ циклов являются равновероятными. Но если элемент в случайной перестановке выбран случайно, то средняя длина содержащего его цикла будет несколько больше, чем п/Н„. Чтобы закончить анализ алгоритмов А и В, следует узнать среднее число едипичимх циклов в случайной перестановке. Это очень интересный вопрос.
Предположим,. мы записали и! перестановок, перечислив сначала те, в которых нет единичных циклов. затем те, в которых есть только один единичный цикл и т. д. Например, для п = 4 это будет выглядеть так. Нет фиксированных элементов: 2143 2341 2413 3142 3412 3421 4123 4312 4321 Один фиксированный элемент: 1342 1423 3241 4213 2431 4132 2314 3124 Два фиксированных элемента: Три фиксированных элемента: Четыре фиксированных элемента: 1243 1432 1324 4231 3214 21Д4 1234 (В этом списке отмечены единичные циклы, т.
е. элементы, которые в результате перестановки остаются на месте (фиксированные элементы).) Перестановки, не имеющие фиксированных элементов, называются беспорядочнмл4и; число таких перестановок — это количество способов твк разложить п писем по и конвертам, чтобы ни одно из них не попало в свой конверт. Пусть Р„ь †чис перестановок из и объектов, имеющих ровно й фиксированных элементов.
Тогда, например, Р40=9, Р42=8, Р42=6, Р4з=О, Р44=1. При изучении приведенного выше списка обнаруживаются главные ссютношения, связывающие эти числа. Можно получить все перестановки с )4 фиксированными элементами, сначала выбирая те )4 элементов, которые нужно зафиксировать (это можно сделать (",) способами), а затем переставляя оставшиеся и — )4 элементов всеми Р)„ь)0 способами, которые больше не оставляют фиксированных элементов. Отсюда Ров — ( ) Р)о-ь)0. (22) Существует также правило, которое говорит о том, что "целое — это сумл40 соста- вляющих его частей": и — Роп + Ро)о-1) + Ршо-2) + Ро)п-3) + ' ' ' .
(23) Подставив (22) в (23) и выполнив простые преобразования, получаем Роо Р40 Р20 Рзо и! = — + и — + и(п — 1) — + и(и — 1) (и — 2) — + О! 1! 2! 3! (24) Эта формула должна быть справедлива для всех целых положительных п. Она уже встречалась ранее, в разделе 1.2.5 (в связи с попытками Стирлинга обобщить факторивльную функцию), а простой вывод ее коэффициентов был приведен в разделе 1.2.б (пример 5). Мы приходим к выводу, что РтО 1 1 — — + +( ')— т (25) Теперь пусть р„ь †вероятнос того, что перестановка из п объектов имеет ровно lс единичных циклов. Так как р„ь = Р„~)п1,из (22) и (25) получаем Ы' 1 1 „„1 р„, = — (1 — — + — —" +(-1)ь-Ь к! 1, 1! 2! (и — /с)!/ (26) Следовательно, производящую функцию С,(г) = р„э + рыб + р„згэ + можно представить в виде 1 1 „1 С„(г) = 1+ — (г — 1) + + — (г — 1)" = ~~~ —, (г — 1)~.
(27) 1! и! 73 о<~<а Из этой формулы следует, что С'„(г) = С„,(г). Воспользовавшись методами, которые применялись в разделе 1.2.10, получим следующие статистические характеристики для числа единичных циклов: (пйп О, аге 1, шах и, бег 1), если и > 2. (28) Несколько более прямой способ подсчета числа перестановок, не имеющих единичных циклов, следует из принципа включения и исключения, который имеет большое значение для многих задач перечисления. Общий принцип включения и исключения можно сформулировать следующим образом. Дано Х элементов и М подмножеств этих элементов 5ы5з,...,5м.
Необходимо подсчитать, сколько элементов не попало ни в одно из этих подмножеств. Пусть (5~ — число элементов множества 5. Тогда искомое число объектов, не принадлежащих ни одному из множеств 5„равно "— Е ~5~+ Е ~5О5~ — .у. 15О5 О5ь~+ ~<,<м ~йг<ьйы ~й «з<ь<м +( — 1) ~5, О" П5м~. (29) (Таким образом, сначала из общего числа Х вычитается количество элементов множеств 5ы, ..,5м; но это меньше искомой величины, так как мы вычли больше, чем нужно.
Поэтому снова добавляем число элементов, которые являются общими для пар множеств, 5 О 5ы для каждой пары 5, и 5ы но зто уже больше искомой величины. Поэтому вычитаем элементы, общие для каждой тройки множеств, и т. д.) Существует несколько способов доказательства этой формулы, и читателю предлагается найти один из них самостоятельно (см. упр. 25). Чтобы подсчитать число перестановок из и элементов, не имеющих единичных циклов, рассмотрим Х = и! перестановок и обозначим через 5, множество перестановок, в которых элемент у' образует единичный цикл.
Если 1 < 7~ < уэ < < ув < и, то количество элементов в 5я О 5м О О 5,„— это число перестановок, в которых 1ы, ..,уь образуют единичные циклы. Очевидно, что оно равно (и — й)!. Таким образом, формула (29) принимает вид и! — ~ ) (и — 1)! + ( ) (и — 2)! — ( ) (п — 3)! + ..
+ ( — 1)" ( ) О1, что согласуется с (25). Принцип включения и исключения был предложен А, де Муавром (А. Йе Мо1чге) [сьь его работу Росгг1пе ог" СЬапсеэ (Еопбоп, 1718), 61 — 63; Згб еб. (1756, переиздано СЬе1эеа, 1957), 110-112]. Но значение этого принципа не было по достоинству оценено до тех пор, пока В. А. Витворт (тг". А.
%Ь!сшогсЬ) не популяризировал и не развил его в своей знамени?юй книге СЬо!се апд СЬзпсе (СашЬгЫбе, 1867). В разделе 5.1 будет продолжено изучение комбинаторных свойств перестановок. УПРАЖНЕНИЯ 1. [02] Рассмотрите преобразование множества (О, 1, 2,3,4,5,8), которое меняет х на 2х шоб 7. Покажите, что это преобразование является перестановкой, и представьте ее в циклической форме. 2. [!О] В тексте раздела показано, как можно присвоить (а,б,с,д,е,2) е- (с,а,7,6,е,а), выполнив ряд операций замены (х < — и) и введя одну вспомогательную переменную й Покажите, как сделать то же самое с помощью ряда операций егаи.иного обмена (х еэ 2) и без вспомогательных переменных.
3. [02] Вычислитепроизведение(", г ' ' ~)х(' г ' ' ~) изапишитерезультатввиде двухстрочной записи. (Ср, с соотношением (4).) 4. [!О] Выразите (а Ь4)(е 7)(а с?)(60) в виде произведения непересекающихся циклов. 5. [М!О] В (3) приведено несколько эквивалентных способов представления одной и той же перестановки в циклической форме. Сколько существует таких представлений перестановки, в которых вообще нет единичных циклов? 8. [М22] Как изменится время выполнения программы А, если отказаться от предположения, что все пустые слова появляются у правого края ввода? 7. [!О] Если иа вход программы А подается произведение перестановок (б), то чему равны величины Х, У, М, М, с! и К из (19)? Каким будет время выполнения программы А без учета ввода-вывода? 8. [22] Можно ли модифицировать алгоритм В так, чтобы просматривать входные данные слева направо, а не справа налево? 9.
[1О] Программы А и В воспринимают одинаковые входные данные и ответ дают, в сущности, в одинаковой форме. Дают ли обе программы е точности один и тот же вывод? и 10. [М22] Рассмотрите характеристики времени выполнения программы В, а именно— величины А, В, ..., 2, о которых шла речь в тексте раздела. Выразите общее время выполнения через величины Х, 1; М, !э', Ь?, 1', определенные в (19), и через Р. Сравните общее время выполнения программ А и В для ввода (б), проведя вычисления, как в упр.
7. 11. [15] Найдите простое правило, по которому можно записать я в циклической форме, если перестановка я задана в циклической форме. 12. [М27] (Транспонированае прямоугольной матрицы.) Пусть матрица (ао) размера т х и, т ф и, хранится в памяти, как описано в упр. 1.3.2-10, так что значение ао находится в ячейке 2 + и(! — 1) + (! — 1), где 1 — это ячейка, в которой содержится ап. Необходимо найти способ трансаонарования этой матрицы, чтобы получить матрицу (Ь, ) размера и х т, где Ь,г = ам хранится в ячейке 2 + т(1 — 1) + (! — 1). Таким образом, наша матрица должна быть трзнспонирована "на себя".
(а) Покажите, что преобразование транспонирования переводит значение из ячейки 2 + х в ячейку Е + (тх гаоб А!) для всех х из промежутка О ( х < А! = тп — 1. (Ь) Обдумайте методы выполнения такого транспонирования с помощью компьютера. ь 13. [М24] Докажите справедливость алгоритма Л. и 14. [Му!] Найдите среднее значение величины Л, которая является одной из составляющих времени выполнения алгоритма Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
