Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 22
Текст из файла (страница 22)
Первой ориентированной на применение компьютеров публикацией о методах комбинаторной генерации стала статья Ч.Б. Томпкннса (С.В. Тсапр1апз) "МасЫпе ассасйв оп ргоЫе|пв |зЬозе тапаЫев аге регпшсабопз" (Машинное решение задач, переменнымн которых являются перестановки) (Ргос. сутр. Арр!!ес! МасЬ., 6 (1956), 202 — 205]. За ней не замедлили последовать тысячи других. Рцд статей Д.Г. Лемера (В.Н. Ье1ппег), особенно "ТеасЫпй сотЬ|пасопа1 сг!сйз со а сотрисег" (Обучение компьнггера комбинаторным трюкам) (Ргос. сутр.
Арр!!ес! Ма|5., 10 (1960), 179-193), оказали исключительно большое влияние на исследования в то время. (См. также Ргос. 1957 Саиаобап Ма|Л. Сопйтевв (1959), 160-173; Ргос. 1ВМ Вс!епв!Нс Сотрисшб Бутрояит сю СотЬ|па!опа! РгоЫетз (1964), 23-30; а также главу 1 книги Арр!!зс! СотЬшасопа! Ма|Летансз под ред. Е.Р. Вес1сепЬасЬ (%йеу, 1964), 5-ЗЦ Лемер оказался важным связующим звеном с предыдущими поколениями.
Так„например, записи в Стэнфордской библиотеке свидетельствуют, что в январе 1932 года он изучал ЬеЛгЬисЛ с)ег СошЬ|па|огйй Э. Нетто. Основные публикации, посвященные рассматривавшимся нами конкретным алгоритмам, упоминались в предыдущих разделах, так что повторять нх здесь нет необходимости. Однако следует упомянуть три книги, которые заслуживают особого внимания, поскольку именно в них были заложены общие принципы. з Е!ешеп|з оу СотЬша|опа! Сошриз!пя Марка Б, Уэллса (Магй В.
%е)(з) (Регйапюп Ргезз, 197Ц, особенно глава 5. з СотЬша|опа! А!8оп|йшв Альберта Ньенхуиса (А1Ъег| Ы!)епЬи1з) и Герберта С. Внльфа (НегЬегз 8. %0!) (Аеас(еш1с Ргезз, 1975). Второе издание книги вышло в 1978 году и содержало дополнительный материал; впоследствии Вильф написал СотЬшв|опл! А!8оп|Лтьт Ап Урс)асе (РЬйаде)рЬ!а: 81АМ, 1989), ° СошЬ!пасопа! А)яог!|Ьтв: ТЛеогу апс! Ргаснсе Эдварда М. Рейнгольда (Ес)- сгзгс( М, Ве1пйоИ), Юрга Нивергельта (Лигй %езегйе11) и Нарсингха Део (ЫагзшйЬ Пео) (Ргепйсе-НаП, 1977), особенно материал главы 5. Роберт Седжвик (ВаЬег| Вес(йеп1с1с) опубликовал первый серьезный обзор по методам генерации перестановок в Сошрис!пя Еиггеуз, 9 (1977), Г3-116, 314.
Второй сделано для вълсс!БГанаФа.оге 94 КОМБИНАТОРНЫИ ПОИСК 7.2.1 вехой стал обзор Карлы Сэведж (Саг!а Вазайе), посвященный кодам Грея [ЯАМ Нег'еп, 39 (1997), 605-629[, Ранее мы уже отмечали, что алгоритмы для генерации объектов, подсчитываемых при помощи чисел Каталана, не были созданы до тех пор, пока разработчики программного обеспечения не ощутили в них потребность. Первые опубликованные алгоритмы не цитировались в разделе 7.2,1.6, поскольку были вытеснены более эффективными методами, однако здесь самое подходящее место упомянуть о них.
Вопервых, Г.Я. Скоинс (Н 1. 8со1пз) привел два рекурсивных алгоритма для генерации упорядоченных деревьев в той же статье, которую мы уже цитировали, говоря о генерации ориентированных деревьев [Масйше 7п1еййепсе, 3 (1968), 43-60[. Его алгоритмы работают с представлением бинарных деревьев в виде битовых строк, что, по сути, эквивалентно польской префиксной записи или вложенным скобкам. Затем Марк Уэллс (Магй 'Ке!1з) в разделе 5.5.4 упоминавшейся выше книги генерировал бинарные деревья, представляя их в виде непересекающихся разбиений множеств. Наконец, Гари Кнотт (Сагу Кпон) [САСМ, 20 (1977), 113-115[ разработал рекурсивные алгоритмы для определения ранга бинарного дерева и поиска бинарного дерева по заданному рангу, представляя деревья при помощи перестановок 41...
д„ из табл. 7.2.1.6-3. Алгоритмы для генерации остовных деревьев заданного графа были опубликованы рядом авторов еще в 1950-е годы; толчок к таким алгоритмам дало изучение электрических сетей. Вот некоторые из самых ранних работ в этом направлении: г(. %йайама, ИЕ Тйвлз., СТ-5 (1958), 122-127; %. Мауеба, ИЕ 2гапв., СТ-6 (1959), 136-137, 394; Н. У7аьапаЬе, ИЕ 7гзлз., СТ-7 (1960), 296-302; Б. НаГбпн, 1. ггапк(1п 1пзизпсе, 272 (1961), 347 — 359. В главах 2 и 3 книги Попа)4 1. КгеЬег апб Поп61аз Н.
Бйпзоп СошЫпагопа( А!8опзйтз: Сепегабоп, Епишегабоп, апс( Яеагсй (СНС Ргаэз, 1999), можно найти полезную информацию по всей рассматриваемой теме. Франк Раски (Ргапй Нпз1сеу) подготовил книгу СошЫпа1оПа1 Сепегабоп, которая будет содержать всестороннее рассмотрение комбинаторных вопросов и исчерпываюшую библиографию по данной теме. Черновики некоторых глав из этой книги можно найти в Интернете.
Упражнения Во многих из предлагаемых упражнений от современного читателя требуется найти и/нли исправить ошибки в литературе давно минувших дней. И цель отнюдь не в том, чтобы, злорадно ухмыляясь, показать, насколько мы в ХХ1 веке умнее, а в том, чтобы понять, что даже пионеры в некоторой области могут оступаться. Полное понимание того, что множество идей ие столь просты, как может показаться сегодняшнему программисту и математику, придет к вам лишь тогда, когда вы обнаружите, как много сил вынуждены были тратить ученые мирового уровня на то, чтобы разобраться с этими новыми концепциями. 1.
[15[ Существует ли понятие "вычислительная техниЫ' в 1 СЫпя? М 2. [МУО] (Генешпческпй код.) Молекулы ДНК представляют собой строки "нуклеотидов" из четырехбуквенного алфавита (Т, С, 5,0), а большинство молекул белков представляют собой строки "аминокислот"' из 20-буквенного алфавита (А, С, .О, Е, Р, сделано для игипа АпГапаса.ога 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 95 С, Н,1, К, Х„М, Ф, Р, ь), В, Е, Т, У, И~, У). Три последовательных нуклеотида обра- зУшт базовый блок — "кодов", а цепочка х191ггхгрггг... ДНК опРеделЯет белок 1 (х1уггг) 1 (хгрггг), где 1 (х,р, г) — элемент в строке г и столбце у матрицы х в массиве (Здесь (Т, С, А,0) = (1,2,3,4); например, Х (САТ) представляет собой элемент в строке 1 и столбце 3 матрицы 2, т.е. Н.) Кодирование выполняется до тех пор, пока кодом не приведет к останавливающему элементу '-'.
а) Покажите, что существует простой способ сопоставить каждый кодом гексаграмме из Х СЬХп8, причем 21 возможный выход (А, С, Ху,..., И', У, — ) соответствует 21 посэедаваше,веной гексаграмме в упорядочении (1) Кинг Веня (К)п8 %еп). Ь) Является ли это открытие сенсационным? 3. [30) Какой вид имеет миллионная строфа из 30 тактов в солексном порядке, аналогичном (2)? Каков ранг ? 4.
[10] Проанализируйте недочеты списка перестановок Донноло (Поппо1о) в табл. 1 б. [16) Где ошибка в списке перестановок пяти нот Кирхера (Кп.сЬег) в (7)? 6. [86) Б своей книге Тгайея г(е 1а Уоюх ег оеэ СХгапеэ (1636) Мерсенн (Мегэеппе) опубликовал таблицу первых 64 факториалов на с. 108-110. Его значение для 64! приближенно равно 2.2 х 10ээ, хотя на самом деле оно должно бьггь равно -1,3 х х 10ээ. Найдите копию этой книги и выясните, где он ошибся. 7.
[80) Какие перестановки множества (1„2, 3, 4, б) "живы-", а какие "мертвы" в соответствии с правилами Секи (Бейб) (8) и (9)? ° 8. [М37) Придумайте исправление, которое нужно внести в правило (9), чтобы процедура Секи стала корректной. 9, [15] Получите из (11) арабский способ написания арабских цифр (О, 1,..., 9). м 10. [НМ27) Каково математическое ожидание количества бросков костей в игре Ьпбпэ С1еЗсабэ для получения всех возможных добродетелей? 11, [81] Расшифруйте вертикальнув таблицу Луллня на рис. 43 справа. Какие 20 комбинаторных объектов она представляет1 Указание: не позволяйте опечаткам ввести вас в заблуждение.
12. [М80) Свяжите универсальный цикл Шиллингера (8с1пПшбег) (13) с универсальным циклом Пуансо (Рошэос) из упражнения 7.2.1.3-106. сделано для иэтэтЛп[апаса,ого РВУ С Р 8 У С Х, 5 Х Я вЂ” И' Х Р Н В 1 Т Ф В Х, Р Н В Х Т Ф В Х Р ь) В Х Т К В Х Р О В М Т К В А Ху С А Ху С А Е С У А Е С 96 КОМВИНАГОРНЫЙ ПОИСК 13. Щ Что ван Шутен (тап БсЬоо1еп) должен был написать вместо (17)? Приведите также соответствующую таблицу для сочетаний мультимножества (а, а, а, Ь, Ь, с). в 14.
[ОО[ Завершите последовательность из 3 95 Пе СошЬшанопе Изкуэрдо ()гх1шегбо): АВС АВВ АВЕ АСВ АСЕ АСВ АПЕ АПВ АПС АЕВ .... 15. [15[ Если все п-сочетания с повторениями х1... х„множества [1,..., т) перечислены в лексикографическом порядке, причем я1 « ° ° х„, то сколько из них начинается с числа у? 16.
[30[ (Нараяна Пандита (Хагауапа РапшФа), 1356.) Разработайте алгоритм для генерации всех композиций числа и из частей, не превышающих с, т.е. всех упорядоченных разбиений и = аг + ° + ам где 1 < ау < о пРи 1 < Г' < $ и пРоизвольном значении С Проиллюстрируйте ваш метод для и = 7 и о = 3.
17. [НМ07[ Проанализируйте алгоритм из упражнения 16. 18. [10[ Шуточный вопрос: Лейбниц опубликовал свою ПВэег1ано Ое Аде СотЫ- патона в 1666 голу. Что особенного в этом году с точки зрения перестановок? 19. [17[ В какой из строф Путеануса (Рпгеапиэ) (20) 'ВЬГ трактуется как — —, а не как 7 20. [М35[ К визиту трех титулованных особ в Дрезден в 1617 году поэт опублико- вал 1617 перестановок гекзаметра Вапс Фг1а )аш Пгшбю, сеп эо) ба1, 1шшпа 1псеш, 'Трое дапы ныне Дрездену„как Солнце дает луч за лучом". [Сгейог К1ерр1э, Ргосеив Роенсие (1,е1рюй: 1617).[ Сколько перестановок этих слов являются гекзаметрами? Указание: строфа имеет двктили в первой и пятой стопах, в остальных стопах— спонден. 21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
