Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007

ББК 32.973.26-018.2.75 К53 УДК 481.142,2 Издательский дом "Вильямс" д ц й С.Н. 2") Вб ПерепОд с анГЛнйсКОГО в )юла)щия заид. техн. наук Я.Б, Красикова ПО общИМ ВОПРОСаы ОбращайтЕСЬ П ИЗдатЕЛЬСКИй дОЫ "ВИЛЬЯМС" ПО )щрвбуг щй))гм)й)апмрцйрюЫай.сощ, ЬЬ)р;//эжаг.мгй)ал)арпЬйнЬщб.сош 115419, Москва, а/и 783) 03150, Киев, а/в 152 Кнут, Дональд Э. К53 Искусство программирования, том 4, выпуск 4. Генерация всех деревьев.

История комбинаторной генерации.: Пер. с англ. — М. ! ООО нИ.Д, Вильямс", 2007. — 160 с.: ил. — Парал. тит. англ. 18ВХ 978-5-8459 — И58-2 (рус.) Эта книга представляет собой один из выпусков очередных томов всемирно известной работы Искрсси)вв программирования, не нужда)ощейся ни в представлении, ни в рекламе.

В данный выпуск вошли разделы четвертого тома, посвященные вопросам генерации всех деревьев, а также обзор истории генерации различных комбинаторпых объектов. Материалы выпуска в будущем войдут в четвертый том серии, посвшценный комбинаторным алгоритмам,— возможно, с определенными дополнениями и исправлениями на основе отзывов читателей данного выпуска. ВВК 32.973.26-018.2.7$ Е) издательский дом "Вильямс", и)ет © Ьу Реагэоп Евосацоп, 1пс., 200В )ЗВН 929-6-9499-1)39-2 (рус.) )ЗВН 0-321-33970-3 (аигл4 Все названия программнмх продуктоэ нвлвются зарегисгрнрованнммн торговыми мвркамн соотиетстзуюжнх 4юрм. Никакак часть явстовжего яздаинн нн в каких целях не может бмть воспроизведена е какой бы то нн бьюо 4юрме и какими бм то ни было средствами, будь то электровнью влн механические, включая 4ютокопмровэпне н запись на магнитные носитель, если иа это иет письменного рвзрюнеиня вздательсюв А44)эоп-ЪУю)еу РнЫМЫнб Союрапу, )пс.

Ащьонэеб )гапе1апоп )гою )Ье Епбаэь !внбпабе мп)юп рнЬВэЬеб Ьу А44)эогь\Ую)еу РпЬВэЬ!пб Союрвпу, 1пс, Сорупбм 45 2006 Ьу Реагэоп Ебпсаиоп, 1вс. АВ Нбьы геэегтеб, Но рагс о) )Ыэ Ьоо)г юву Ье гергги)псеб ог )гапэпп))ад Ы впу )оип ог Ьу впу гпеелэ, е)ес)гоп!с ог гпесЬапгса), 1пс)ибюб рЬогосоруыб, гесопвхй ог Ьу впу )п)оппвноп е)огабе гещегв! эуэ!ею, и!)Ьсю) ропп)яаоп Вою гье РнЫЬЬег, ИН)мэ )о )Ьм Ьооь веге оЬ)вюеб Ьу аггвпбеюеп) наЬ Абб)эсп-))гю)еу ! опбюап, )пс. нвеэьги !апбнабе еб!Воп рпы)эьеб ьу %'ш)впм Рпы)эыпб нонэе ассопяпб )о )ье Абгееюэп! збэь Ва) еп)егрг)эеэ ьиегпа))опа1, соруг16ьэ 4!) 2903 Оглавление Предисловие Ответы н упражнениям Предметный уназатеиь 1А6 7 Комбииаторвый поиск 7.2 Генерации всех возможных объектов 7.2.1 Геиеревдя основных комбинаторных обьектов 7.2.1,1 Генерация всех я кортежей 7.2.1.2 Генерация всех перестановок 7.2.1.3 Генерация всех сочетаний 7.2.1.4 Генерация всех разбиений 7.2.1.5 Генерация всех разбиений множеств 7.2.1.6 Генерация всех деревьев 7.2.1.7 Исторические н иные сведения и П Г1 11 11 11 12 12 12 67 От издательства 113419> Москва, а/я 783 03150, Киев,а/я 132 Вы, читатель этой книги, и есть главный ее критик и комментатор.

Мы ценим ваше мнение и хотим знать, что было сделано нами правильно, что можно было сделать лучше и что еще вы хотели бы увидеть изданным нами. Нам интересно усльппать и любые другие замечания, юторые вам хотелось бы высказать в наш адрес. Мы ждем ваших комментариев и надеемся на них. Вы можете прислать нам бумажное или электронное письмо, либо просто посетить наш%еЬ-сервер и оставить свои замечания там. Одним словом, любым удобным для вас способом дайте нам знать, нравится или нет вам эта книга, а также выскажите свое мнение о том, как сделать наши книги более интересными для вас. Посылая письмо илн сообщение, не забудьте указать название книги и ее авторов, а также ваш обратный адрес.

Мы внимательно ознакомимся с вашим мнением и обязательно учтем его при отборе и подготовке к изданию последующих книг. Наши координаты: Е-шю1: 1пхойв1111аяврпЫйвв1вй. сои %%%: ивер;//ввв.вШйаиврпЬ11впйпй.сои Информация для писем: из России: из Украины: П редисловие Я люблю работать в самых разных областях — зто позволяет мпе "размазать" мои ошибки более тонким слоем... — Виктор Кля ~эстет Кйе/ Эта брошюра представляет собой четвертый выпуск книги Искусстпео программирования, пюм 4. Комбииашоримг алгорипьим. Как пояснялось в выпуске 1 к тому 1, я издаю материалы в такой форме в связи с тем, что работа нгд четвертым томом займет еще много лет.

Я не могу заставлять читателей ждать так долго; кроме того, мие нужна обратиая связь от читателей. В этом выпуске содержатся разделы 7.2.1.6 и 7.2.1.7 очень большой главы, посвящеииой комбииаториому поиску. В окоичательиом виде глава 7 должна будет состоять из трех томов ~4А, 4В и 4С) — коиечио, если это позволит мое здоровье. Глава иачиется с краткого обзора теории графов, после которого в разделе 7.1 будут рассматриваться вопросы работы с битами и алгоритмы для работы с булевыми фуикциями. Раздел 7.2 посвящен генерации всех возможиых объектов и начинается с подраздела 7.2.1 — генерации основных комбияаторных объектов.

В подразделах с 7.2.1.1 по 7.2.1.6 детально рассматриваются вопросы о генерации всех п-элемеитиых кортежей, перестановок, сочетаний и разбиеяий. Выпуск 4 содержит разделы 7.2.1.6, посвященный генерации различных древовидных структур, и 7.2.1.7, темой которого является история комбииаториой генерации. Раздел 7.2.2 будет посвящеи перебору с возвратом в целом. Набросок содержания всей главы 7 можно найти на%еЬ-сайте книги №кусстео программирования (Мср: //вви-св-таси1су. всалтог4. еби/ "кппсв/скосу. псяЦ. Написание этого материала доставило мие такое же удовольствие, как испытаниое миою много лет вазед при написаиии второго тома ггскуссшва программироевиил.

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

Я уже давно хотел написать о генерации деревьев, потому что древовидные структуры занимают особое место в сердце каждого программиста. Хотя в цепом сделано для эуэуьулн$апа1а.ого 8 ПРЕДИСЛОВИЕ я доволен изложенным в разделах 7.2.1,1-7.2.1.5 материалом о классических комбинаторных структурах, таких, как кортежи, перестановки, сочетания и разбиения, все же самый лакомый кусочек я приберег напоследок. И вот наступило время для этого десерта. С 1994 года я читаю ежегодную еЛекцию о рождественской елке" ~ в Стэнфордском университете, рассказывая о замечательных фактах, касающихся деревьев, о которых я узнал в течение последнего года, и вот наконец я могу изложить все эти лекции в письменном виде.

Как и любой дежрт, эта тема очень "сытная' и приносит немало удовольствия. Теория деревьев, помимо прочего, связывает воедино ряд концепций из разных областей программирования. Раздел 7.2.1.7, посвященный истории комбинаторной генерации, принес особое удовлетворение другой, "гуманитарной", половине моего мозга, поскольку он наполнен поэзией, музыкой, религиозными представлениями, философией, логикой и интеллектуальными играми нз разных культур со всего света. Корни комбниаторного мышления очень глубоки. Я не претендую на полноту, но думаю, что достаточно полно изучил эту тему, чтобы собрать все изученное вместе. Первоначэлыю я намеревался выделить этому материалу более скромное место, но когда увидел, насколько фундаментальны собранные здесь идеи, то понял, что одно лишь беглое упоминание о них вряд ли удовлетворит меня, Я благодарю Франка Раски 1гЪшк Впэкеу) за смелое решение предложить ранние черновые варианты этого материала студентам и за то, что он поделился со мной результатами этого эксперимента.

Мне помогли и многие другие читатели моих черновиков, особенно относящихся к разделу 7.2.1.7, где мне часто была нужна помощь из-за ограниченного знания других языков. Я с удовольствием уплачу 2 доллара 56 центов тому, кто первым сообщит мне о любой замеченной в данном выпуске ошибке, неважно какой — типографской, технической или исторической. Все существенные предложения по улучшению текста я оцениваю в 32 цента каждое. (Кроме того, если вы найдете лучшее решенпе упражнення, то сможете покрыть себя неувядающей славой — ваше имя будет опубликовано в окончательном издании книги.:-) Перекрестные ссылки на пока что не написанный материал могут выглядеть в тексте как 'ОО', это заполнитель, который будет заменен реальным числом в будущем.

Приятного чтения! Стэнфорд, Калифорния Июнь 2005 Д. Э. К. Об обозначениях. В начале главы 7 я определил некоторые операции иад графами, для которых в настоящее время в литературе встречаются разные обозначения. В моей книге, если С вЂ” граф с вершинами У = (пм..., н 1, а Н вЂ” граф с вершинами и' = ~пи...,п„1, то: ° С+ Н является суммой, или соединением С и Н: этот граф содержит Рта + и вершин У О 1г и ребра С и Н; гОпределенная игра слов — в оригинале "Оьпеспцм ггее!есспге", те. о Рождественском дереве.

Название можно также перевестп и как "Лекция у Ропщественскоа елки". — Примеч. пер. ткоиечно же, имеется в виду оригинальное издание. — примое. пер. сделано для эрьлкпИапа1н.ого ПРЕДИСЛОВИЕ 9 е С + Н является сбъедииеиием (сосуммой (созшп)) С и Н, т.е. дополнеияем соединения ик дополиеиий (его ребрами являются ребра С и Н плюс все ребра пу-ее)' е С х Н представляет собой декартово произведеиие С и Н" .в нем содержится гоп верщип У х Ъ', а ребрами являются (и, е) — (и',е), когда С имеет ребро и — и', и (в, е) — (и, е'), когда ребро е — е' содержится в Н", е СОН вЂ” прямое произведение, или конъюнкция, С и Н: его вершииами яв- ляются У х У, а ребро (и, и) — (и', е') содержится в нем тогда и только тогда, когда в С имеется р~бро и — а', а в Н вЂ” ребро и — с', ° СФН вЂ” сильное произведение С и Н, объединяющее ребра С х Н и СОН; по аналогии с сосуммой имеются различные виды сопроизведепий.