22. {М28] Пусть даны описания весьма большого числа ориентированных графов. Как можно сгруппировать изоморфные графы? (Два ориентированных графа называются изоморфными, если суш;ествует взаимно однозначное соответствие межда- их вершинами и взаимно однозначное соответствие между их дугами, причем эти соответствия сохраняют инцидентность вершин и дуг.)

23. [30] В некоторой группе из 4 096 человек каждый имеет около 100 знакомых. Был составлен список всех пар людей, знакомых друг с другом. (Это отношение симметрично, т. е. если х знаком с у, то и у знаком с х. Поэтому в списке содержится примерно 200 ООО пар.) Придумайте алгоритм, который по заданному к выдавал бы все клики из к человек. {Клика - это группа людей, в которой все знают друг друга.) Предполагается, что не бывает слишком больших клик (размером более 25).

► 24. [30] Три миллиона человек с различными имена.ми были уложены рядом непрерывной цепочкой от Нью-Йорка до Калифорнии. Каждому из них дали листок бумаги, на котором он написал свое имя и имя своего ближайшего западного соседа. Человек, находившийся в крайней западной точке цепи, не понял, что ему делать, и выбросил свой листок. Остальные 2 999 999 листков собрали в большую корзину и отправили в Национальный архив, в Вашингтон, округ Колумбия. Там содержимое корзины тш;ательно перетасовали и записали на магнитные ленты.

Специалист по теории информации определил, что и.меется достаточно сведений для восстановления списка людей в исходном порядке. Программист нашел способ сделать это менее чем за 1 ООО просмотров лепт с данными, используя лишь последовательный доступ к файла.м на лентах и небольшой объем оперативной памяти. Как ему это удалось?

[Другими словами, как, имея расположенные произвольным образом пары {xi,Xi+i), 1 < г < N, где все Xi различны, получить последовательность xiX2 .xn, применяя лишь методы последовательной обработки данных, которые пригодны для работы с магнитными лентами? Это сортировка в случае, когда трудно определить, какой из двух ключей предшествует другому; мы уже поднимали этот вопрос в упр. 2.2.3-25.]

25. [М21] {Дискретные логарифмы.) Пусть известно, что р - простое число (довольно большое), а о - первообразный корень по модулю р. Следовательно, для любого Ь в диапазоне 1 < 6 < р суш;ествует единственное п, такое, что а" modp = Ь, 1 < ?i < р. (Это п называется индексом Ь по модулю р по отношению к а.) Как по заданному b найти п менее чем за П(п) шагов. [Указание. Пусть т = \/p. Попытайтесь решить уравнение

тщ 5а-П2 (до модулю р) ПрИ Q <П1,П2 < т]

*5.1. КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК

Перестановкой конечного множества называется некоторое расположение его элементов в ряд. Перестановки особенно важны при изучении алгоритмов сортировки, так как они служат для представления неупорядоченных исходных данных. Чтобы исследовать эффективность различных методов сортировки, нужно уметь подсчитывать количество перестановок, которые вынуждают повторять некоторый шаг алгоритма определенное число раз.

Мы уже не раз встречались с перестановками в предыдущих главах. Например, в разделе 1.2.5 обсуждались два основных теоретических метода построения п\ перестановок п объектов; в разделе 1.3.3 были проанализированы некоторые алгоритмы, связанные с циклической структурой и мультипликативными свойствами перестановок; в разделе 3.3.2 изучались их серии монотонности. Цель настоящего параграфа - описать другие свойства перестановок и рассмотреть общий случай, когда допускается наличие одинаковых элементов. Попутно мы. многое узнаем о комбинаторной математике.

Свойства перестановок настолько красивы, что представляют и самостоятельный интерес. Удобно будет дать их систематическое изложение в одном месте, а не разбрасывать материал по всей главе. Читателям, не имеющим склонности к математике, а также тем, кто жаждет поскорее добраться до самих методов сортировки, рекомендуется перейти сразу к разделу 5.2, потому что настоящий раздел непосредственного отношения к сортировке почти не имеет.

*5.1.1. Инверсии

Пусть aia2...an - перестановка множества {1,2,..., п}. Если i < j и щ > aj, то пара {ai,aj) называется инверсией перестановки; например, перестановка 314 2 имеет три инверсии: (3,1), (3,2) и (4,2). Каждая инверсия - это пара элементов, "нарушающих порядок"; следовательно, единственная перестановка, не содержащая инверсий, - это рассортированная перестановка 1 2... гг. Такая связь с сортировкой и является главной причиной нашего интереса к инверсиям, хотя это понятие уже использовалось, когда мы анализировали алгоритм динамического распределения памяти (см. упр. 2.2.2-9).

Понятие инверсии ввел Г. Крамер в 1750 году в связи со своим замечательным правилом решения линейных уравнений [Intr. а Г Analyse des Lignes Courbes Algebriques (Geneva, 1750), 657-659; см. также Thomas Muir, Theory of Determinants 1 (1906), 11-14]. В сущности, он определил детерминант п х гг-матрицы следующим образом:

•-пап ,

= (-1)-(°°-

\Хп1 Хп2 пп /

где сумма берется по всем перестановкам aj аг ... а„ из {1,2,..., п}, а inv(ai аг -.. а„) - число инверсий в перестановке.

Таблица инверсий bi Ьг • • перестановки aj аг ... а„ образуется, если определить bj как число элементов слева от j, которые больше, чем j. Другими словами, bj - число инверсий, второй элемент которых равен j. Отсюда, например, следует, что таблицей инверсий перестановки

591826473 (1)

будет

2 3 6 4 0 2 2 1 0, (2)

поскольку 5 и 9 расположены левее 1; 5, 9, 8 - левее 2 и т. д. Всего эта перестановка имеет 20 инверсий. По определению числа bj всегда удовлетворяют неравенствам

0<6i<n-l, 0<б2<п-2, 0< Ьп-1 < 1, Ьп = 0. (3)

Пожалуй, наиболее важный факт, касающийся перестановок и установленный Маршаллом Холлом (Marshall Hall), состоит в то.м, что таблица инверсий единственным образом определяет соответствующую перестановку. [См. Ргос. Symp. Applied Math. 6 (American Math. Socletj, 1956), 203.] Из любой таблицы инверсии bib2 .. .bn, удовлетворяющей условиям (3), можно однозначно восстановить перестановку, которая ее породила, путем последовательного определения относительного расположения элементов п,»г-1,...,1 (в этом порядке). Например, перестановку, соответствующую (2), можно построить следующим образом: выпишем число 9, затем разместим 8 после 9, поскольку bs = 1. Аналогично установим 7 после и 8, и 9, поскольку 67 = 2. Так как 6б = 2, то 6 должно следовать за двумя уже вьшисанны.ми нами числами; таким образом, имеем промежуточный результат

9 8 6 7.

Продолжим, приписав 5 левее, поскольку 65 = 0; поместим 4 вслед за четырьмя из уже записанных чисел, а 3 - после шести выписанных чисел (т. е. в правый конец) и получим

5 9 8 6 4 7 3.

Вставив аналогичным образом 2 и 1, придем к (1).

Такое соответствие важно, потому что часто можно заменить задачу, сформулированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий, которая, возможно, решается проще. Рассмотрим, например, самый простой вопрос: сколько существует перестановок множества {1,2,..., п}? Ответ должен быть равен числу всевозможных таблиц инверсий, а их легко пересчитать, так как bi можно выбрать п способами, 62 независимо от 61 - n - 1 способами, ..., а 6„ - единственным способом; итого получаем n(n -1)... 1 = n! различных таблиц инверсий. Таблицы инверсий пересчитать легче, потому что значения Ьк полностью не зависят друг от друга, в то время как должны быть все различны.

В разделе 1.2.10 мы рассматривали задачу о числе локальных максимумов перестановки, если читать ее справа налево. Иными словами, требовалось подсчитать количество элементов, каждый из которых больше любого из следующих после него. (Например, правосторонние максимумы в (1) - это 3, 7, 8 и 9.) Оно равно количеству индексов j, таких, что bj имеет максимальное значение п - j. Так как hi будет равно n - 1 с вероятностью 1/п и (независимо) 62 будет равно п - 2 с вероятностью l/(n - 1) и т. д., из рассмотрения инверсий ясно, что среднее число правосторонних максимумов равно