Эксперименты Кима Д. Гибсона (К. D. Gibson), проведенные в 1967 году, показали, что вторая по величине группа пятибуквенных анаграмм из общеупотребительных слов - это LEAST, SLATE, STALE, STEAL, TAELS, TALES, TEALS. Ho если воспользоваться более обширным словарем, то в нее можно добавить слова ALETS (стальные наплечники), ASTEL (осколок), ATLES (намерения), LAETS (люди, занимающие промежуточное положение между рабами и Свободными гражданами), LASET (горностай), LATES (нильский окунь), LEATS (канавы), SALET (средневековый шлем), SETAL (относящийся к остюкам), SLEAT (подстрекать), STELA (колонна, стела) и TESLA (единица измерения магнитной индукции). Если добавить сюда еще и устаревшие написания слов "settle" и "teasel" (SATEL, TASEL и TASLE), то получим в результате 22 слова из тех же букв, ни одно из которых не представляется в орфографическом словаре прописными литерами. Потратив еще немного времени, можно добавить в набор и слово "t(esl! из староанглийского языка, "altes" - из немецкого и "Madame de Stael" - из французского! Набор {LAPSE, LEAPS, PALES, PEALS, PLEAS, SALEP, SEPAL} также можно расширить, по крайней мере, до 14 слов, если всерьез взяться за специальные словари. [См. Н. Е. Dudeney, 300 Best Word Puzzles, edited by Martin Gajrdner (New York: Chas. Scribners Sons, 1968), Puzzles 190 and 194; Ross Eckler, Making the Alphabet Dance (N.Y.: St. Martins Griffin, 1997), Fig. 46c.]

Первой и последней анаграммами среди найденных наборов из пятибуквенных анаграмм в английском языке длиной не менее трех элементов являются {ALBAS, BALAS, BALSA, BASAL} и {STRUT, STURT, TRUST}, если не принимать во внимание подходящих имен собственных. Если же снять это ограничение, то имена Alban, Balan, Laban и Nabal образуют набор, занявший теперь первое место {ALBAN,BALAN, BANAL, LABAN,NABAL,NABLA}. Самый впечатляющий пример длинных анаграмм в английском языке дают математические термины: {ALERTING, ALTERING, INTEGRAL, RELATING, TRIANGLE}. Сюда можно добавить и австралийскую рыбу TERAGLIN.

Можно ускорить процесс, вычисляя f{a) - (h{a\) -t- h{a2) + • • -t- Ь(аъ)) modm, где a\,... ,аь - числовые коды букв слова а, а (h{\), h{2),...) представляют собой 26 случайно выбранных констант; здесь тп - длина машинного слова. В результате сортировки файла (/(а),а) все анаграммы будут собраны вместе; после этого для всех случаев /(а) = /(/3) нужно убедиться в том, что найдена действительно анаграмма, т. е. а - j3. Значение /(а) вычисляется существенно быстрее, чем а, и этот метод позволяет избежать вычисления а для большинства слов а из файла.

Замечание. Аналогичным методом можно воспользоваться, если нужно собрать все множества записей, имеющих равные многословные ключи (oi,..., an). Предположим, что нам безразличен порядок записей, важно только, чтобы записи с равными ключами располагались подряд. В этом случае иногда удобно выполнить сортировку по однословному ключу (oia;"" +022:"" + -bOn) mod т, где х - любая фиксированная величина, вместо того чтобы сортировать по исходному многословному ключу.

22. Найдите инварианты графов (т. е. функции, принимающие равные значения на изоморфных ориентированных графах) и выполните сортировку по этим инвариантам, чтобы отделить одну от другой группы "явно неизоморфных" графов. Далее приводятся примеры инвариантов, (а) Представьте вершину Vi в виде пары (ai,6i), где а; - полустепень захода, а 6{ - полустепень исхода вершины, после чего рассортируйте пары {ai,bi) в лексикографическом порядке. Полученный файл представляет собой инвариант изоморфных графов, (б) Представьте дугу из ы к Vj в виде совокупности (oi,6,,Oj,6j) и рассортируйте эти тетрады в лексикографическом порядке, (с) Разделите ориентированный граф на связанные компоненты (см. алгоритм 2.3.3Е), определите инварианты каждой компоненты и любым способом рассортируйте эти компоненты в порядке инвариантов. (См. также ответ к упр. 21.)

в общем случае после сортировки ориентированных графов по инвариантам необходимо дополнительно проанализировать, являются ли графы с равными инвариантами в самом деле изоморфными. При выполнении этого анализа могут пригодиться и сформированные инварианты. В случае свободных деревьев можно найти "характеристические" или "канонические" инварианты, которые полностью характеризуют дерево, так что необходимость в дополнительном анализе исчезнет. [См. J. Hopcroft, R. Е. Tarjan, Compiexity of Computer Computations (New York: Plenum, 1972), 140-142.]

23. Один из способов выполнения этого упражнения - сформировать файл, содержащий все клики из трех человек, преобразовать его в файл, содержащий все клики из четырех человек, и т. д.; если клики не слищком велики, этот метод вполне подойдет. (С другой стороны, если есть клика размером п, то найдется, по крайней мере, (]J) клик размером к; так что этим методом не удастся получить требуемый результат, даже если п приблизительно равно 25 или более того.)

Если имеется файл, в котором перечислены все клики размером (k - l) в виде (oi,..., Ofc-i), где oi < • < Ofc-i, то клики размером к можно отыскать следующим образом: (i) сформировать новый файл, в который включить элементы (Ь,с,oi,... ,04-2) для каждой пары клик размером (А; - 1) в виде (щ,... ,ak-2,b), (oi,...,0-2,с), где Ь < с; (ii) рассортировать этот файл по первым двум компонентам; (iii) для каждого элемента (6,с,oi,... ,а 2) этого нового файла (при том что пара (6,с) принадлежит исходному файлу знакомств) вывести в качестве результата клику (oi,... ,0-2,6, с) размером к.

24. (Это решение предложено Норманом Харди (N. Hardy) (1967).) Скопируем исходный файл; рассортируем одну копию по первым компонентам, а другую - по вторым. Теперь можно, просмотрев последовательно эти два файла, создать новый, в который включить все пары {xi,Xi+2), 1 < г < N-2, и найти {xn-i,xn)- Пары (N-1, x-i) и {N,xn) следует записать в еще один файл.

Далее процесс продолжается по индукции. Предположим, файл F содержит все пары {xi,Xi+t), 1 < г < Л - t, в произвольном порядке, а файл G содержит все пары {i,Xi), N - t < i < N, упорядоченные по вторым компонентам. Пусть Я - копия файла F; рассортируем Н по первому компоненту, а F - по второму. Просмотрим теперь F, G, и Я и сформируем два новых файла F и G следующим образом. Если текущие записи файлов F, G, Н равны соответственно (ж,ж), (у,у), {z,z), то:

i) если х = Z, выведем {x,z) в F и перейдем дальше в файлах F к Н;

ii) если х = у, выведем (y-t, х) в С к перейдем дальше в файлах F и G;

iii) если ж > у\ перейдем дальше в файле G;

iv) если ж > Z, перейдем дальше в файле Н.

Когда дойдем до конца файла F, рассортируем G по вторым компонентам и сольем с ним G; затем заменим t на 2t, F на F, G на G.

Таким образом, t принимает значения 2, 4,8,...; при фиксированном t для сортировки необходимо выполнить 0(log N) проходов. Следовательно, общее число проходов будет 0{{logN)). В конце концов выполнится t > N и файл F опустеет; тогда останется только рассортировать G по первым компонентам.

25. (Идея решения принадлежит Д. Шанксу (D. Shanks).) Подготовьте два файла, один из которых содержит числа а"" modp, а другой - 6а~" modp, О < п < т. Рассортируйте оба файла и найдите общий элемент.

Замечание. В результате время выполнения 0(р) в худшем случае сократится до ©(vlogp). Возможно и дальнейшее повышение производительности; например, несложно за logp шагов проанализировать, является ли п четным, проверив, какое из равенств 5(р-1)/2 ijiQjip = 1 и (р-1) имеет место. В общем случае, если / является любым делителем

р - 1, а d - любым делителем gcd(/, п), можно аналогичным образом найти {n/d) mod /, отыскав значение Ь-~ - в таблице длиной f/d. Если простыми делителями р-1 являются qi < q2 < < qt, причем, если qt - мало, можно быстро вычислить п, выполняя поиск разрядов справа налево в представлении со смешанными основаниями qi, ,qt- (Эта идея принадлежит Р. Л. Сильверу (R. L. Silver), 1964; см. также S. С. Pohlig, М. Hellman, IEEE Transactions IT-24 (1978), 106-110.)

Джон М. Поллард (John М. Pollard) нашел довольно элегантный способ вычисления дискретных логарифмов, требующий порядка 0{у/р) операций mod р при малых затратах памяти. Способ основан на теории случайных отображений (random mappings). См. Math. Сотр. 32 (1978), 918-924, где он предложил еще один метод, базирующийся на числах Tij = г- modp, которые имеют только малые простые делители.

Асимптотически более быстрые методы обсуждаются в ответе к упр. 4.5.4-46.

РАЗДЕЛ 5.1.1

1. 205223000; 27354186.

2. bi = (т - 1) mod п; bj+i {bj + m - 1) mod (n - j).

3. aj = an+i-j ("отраженная" перестановка). Эту идею использовал О. Теркем (О. Terqu-em) [Journ. de Math. 3 (1838), 559-560] для доказательства того, что среднее число инверсий в случайной перестановке равно (j).

4. Cl. Установить хо <- 0. (Если возможно, желательно на последующих циклах, когда

1 < j < п, использовать для Xj ту же память, что и для bj.)

С2. При к = п, п-1,..., 1 (именно в этом порядке) выполнить следующее: установить j <- О, затем ровно Ьк раз установить j <- Xj, затем установить Хк <- Xj и Xj <- к.

СЗ. Установить j <- 0.

С4. При к - 1,2,... ,п (именно в этом порядке) выполнить следующее: установить ак <- Xj, затем установить j xj. В упр. 5.2-12 показано, как экономно использовать память.

5. Пусть а - цепочка упорядоченных пар целых неотрицательных чисел [т\,п\]... [тк,Пк]; обозначим через а = к длину цепочки а, а через е - пустую (длиной 0) цепочку. Рассмотрим двоичную операцию о, рекурсивно определенную на парах таких цепочек следующим образом:

боа = аоб = а;

т,п]{а о {[т-т,п])), если m < т.

{[т,п]а)о{[т,п])= . , i i й ,

\[m,n]{([m-m-l,n\a)of)), если m > m .

Из такого определения операции следует, что время, необходимое для вычисления а о уЗ, пропорционально а о /3 = а + /3. Более того, можно показать, что операция о ассоциативна и что [6i,l] о [62,2] о ••• о [Ьп,п] = [0,ai][0,a2]... [0,ап]. Выражение в левой части можно вычислить за fig п] проходов, комбинируя на каждом из них пары в цепочках, т. е. всего за 0(п log п) шагов.

Пример. Начав с (2), зададимся целью вычислить [2,1] о [3,2] о [6,3] о [4,4] о [0,5] о [2, 6] о [2, 7] о [1, 8] о [О, 9]. После первого прохода это выражение преобразуется в [2,1][1, 2] о [4, 4][1, 3] о [О, 5][2, 6] о [1, 8][0, 7] о [О, 9]. Второй проход преобразует его в [2,1][1, 2][1, 4][1, 3] о [О, 5][1,8][0, 6][0, 7] о [О, 9]. Третий проход приведет к [О, 5][1,1][0, 8][0, 2][0, 6][0, 4][0, 7][0, 3] о [0,9]. После четвертого прохода получим (1).

Обоснование. Цепочка наподобие [4,4][1,3] представляет "uuuu4u3u°°", где "□" означает пропуск; операция а о /3 вставляет пропуски и заполнения из /3 на место пропусков в а.