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

К2. [Выполнено?[ (В этот момент связи ЬоЬ1... Х э„представляют собой случайное а-узловое бинарное дерево.) Завершить работу алгоритма при а = № КЗ. [Продвижение.[ Пусть Х вЂ” случайное целое число между О и 4а+1 включительно.Установитьа -а+1,6 -Хшод2,к — [Х/2[,Ьз -ь -2а Хз -1+ь'-Хю Ьь +- 2а — 1 и вернуться к шагу К2. 1 сделано для ькьнъЛпХапаса.огя Обратите внимание, что каждое декорированное дерево получается ири помощи данного процесса единственным путем, поскольку предшественник каждого дерева должен быть деревом, которое получается путем вычеркивания листа с максимальным номером. Таким образом, построение Реми дает равномерно распределенные декорированные деревьв; и если проигнорировать внешние узлы, то мы получим случайные бинарные деревья обычного, недекорированного аида.

Один привлекательный способ реализации процедуры Реми состоит в использовании таблицы связей ХеХь... Ьз„, в которой внешние узлы (листья) имеют четные номера, а внутренние (ветвления) — нечетные. Корневым узлом является узел Ье; левым и правым дочерними узлами внутреннего узла 2Й вЂ” 1 являются соответственно Хзь 1 и Х,м для 1 < й < а.

В этом случае программа получается короткой и приятной, 30 КОМБИНАТОРНЫЙ ПОИСК 7,2.1 10 ОО 01 11 (35) В общем случае мы получаем шаблон рождественской елки порядка и + 1, беря каждую строку 'от о» ... о шаблоиа порядка и и заменяя ее двумя строками. гг»0 ... о' 0 ог0 о»1 ... ов-г1 оэ1 (При з = 1 первая из зтих строк опускается.) Действуя таким образом, мы получим пример шаблона порядка 8, приведенный в табл. 4. По индукции легко убедиться в следующем: !) каждая из 2" битовых строк появляется в шаблоне равно одии раз; й) битовые строки, содержащие и единиц, находятся в одком и том же столбце; ш) в пределах каждой строки каждая битовая строка получается из предыдущей путем единственного изменения 0 ва 1, Если рассматривать битовые строки как представляющие подмножества множества (1,..., и), где единичные биты указывают члены миожества, то свойство (йг) гласит, что каждая строка представляет цепочку (сЬаш), в которой каждое подмножество покрывается следующим за иим.

Используя символьную запись из раздела 7.1.3, можно записать: каждая строка ог гг» ... о, обладает тем свойством, что о С о +г и и (тутг) = и (оу) + 1 при 1 < у < ш Свойства (!) и (й) говорят о том, что если пронумеровать столбцы от 0 до и, то в столбце /с имеется ровво (а) элемеитов. С учетом того, что каждая строка отцеитрироваиа по столбцам, зто наблюдение доказывает, что общее количество строк, как и утверждалось, равно пшхокак„("„) = (1„~ ). Обозначим зту величину квк М„. Множество битовых строк С называется илашшером (с!пс»ег)», или оаитицепочкой подмножеств", если его битовые строки иесравиимьг в том смысле, что о (ь т, где о и т — рвзличиые злемеиты С.

Знаменитая теорема Эмануила Спериера (Ешаппе! 8регпег) ]Май. Яе!»всйг!й, 27 (1928), 544-548] утверждает, что ви один клаттер на »Это иазваиие выбрело из сеитимеитальиых соображевий, поскольку аиешиий вяд шаблона иапоминает елку, а кроме того, вта тема была предметом девятой ежегодной ".текции рождестаеиской елки" автора в Стеяфордском университете в декабре 2002 года. здословио — помеха, шум. — Примеч.

пер. сделано для и»йж!атанаса,ого еЦепочкп подмножеств. Теперь, когда мы прочно усвоили получение деревьев и строк скобок, самое время перейти к рассмотрению шабаогга розог)еспгоемской елки (СЬпз»шав ггее раЫ»егп)», который представляет собой замечательный способ размещения всех 2" битовых строк длиной и в ( „" ) строках и и+ 1 столбцах, открытый де Брейиом (г!е Вгш)п), вап Эббенхорст Теибергеи (тап ЕЬЬепЬогзс ТепйЬегйеп) и Круйсвейкам (Кгпуеш!1!с) ]№епш АгсЫег" тоог Ят!з!где, (2), 23 (1951), 191-193]. Шаблон рождественской елки порядка 1 представляет собой единственную строку '0 Г; шаблон порядка 2 имеет вид Таблице 4. Шаблон рождественской елки поридка 8 ИИО1ОЮ Ю1О1ОО1 ииопоо ЮН2ОЮ1 Ю1ООПО !а!ооон юпоо!о 1ОПООО! !Оно!00 иииани 1001опо ыо!ооп юшаю 1аопоо1 10оп010 1ООО1О П 100ШОО 1ОООПО1 1ОООШО юооош поонио НОО1001 паап оо пооани пооопо пооооп ПО! ООЫ ПО1ООО1 поюню О!ОНИО1 оииопо О1ОНЮП попоао О!ОПОО1 ОЮПО1О 010010П о!ошао О10ОПО1 оиюшо онюаш шоеио шоаю1 П100100 апоо1о1 опоопо опеюп шоиюо ОПО1ОО1 опонио 0010!ОП опопао ОО1О ПО! оо1ашо 00100П1 Ш !ОООО ОШООО1 ОШОО1О аопооп опниоо ООПО!О1 оо папа оаиош ош1аоо ООШОО1 ООШО1О 000110П оошию ооошо! ааош!о оооопп юниооо 1ОЮЮП !онюню 1о!оаою 1010ЕЮО Ю1ООЕИ !опию! 1О1ОШО Ы1ОВШ Ю1ОПП юпаоп нииюоо нкионю нюииио 1оонюоо 200!ею! ЮПО1О1 1ОПОПО 1ОО1ОШ 1ОПОШ 10011000 100010!о июо иди 1ОООПОО 1ООЕИО1 июоопо !ааааа п 1ошаи 1ОШО1О нюпоп 1ОШ1ОО нюша! 1ООППО !ооопп 1ОООНЮО 1ОШОП !ОООО!ОО 1оаоаио июоаоао юоооеи 1ОШИИ !ОП ШО ИЮШП 1ОШШ П001000 паоюп ПООПО1 поошо пооош поопп 11оао1оо П000010 поаюоа поаюо1 но!еюо ПО! ООП оииоию О!0!а!20 о1оиюоо о1анюо1 ПОЮЮ1 ПО1ОПО ОЮ1ОШ ПОЮШ оюпооо О1ООИИО 01ао1оо1 оиюпоо 01ооани о!еюпо онюооп попаи попо!о они!Оп ПОП100 О1ОШО1 О1ОШЮ О!ООПП онюиюо попоп 0!ею!00 О1Е22Ю10 оиюоооо 01оо2юо! ПОШО1 поппо оюшп попш П100000 П1000П опеиоо опооою ОПООООО ОПЕЮ01 П 100101 П1ООПО опоош шоош опоиюо ООНИО1О 00101001 еиопоо ОО ив!О! оо1оопо оонюоп шо1001 Ш 0!О!О опоюп шопоо ОПОПО1 апоша ЕИОШ1 ооииооо ШО1ОП ООИЮ100 00100010 аиооооо ооиюоо1 ШОПО1 шоша анап п шош1 Ш 10001 ш1аио ошооп шииоо ОПИИО1 ошопо оопош шпею ОШИЮ1 ошиио оошоп опшао ЕИШО1 оопшо ОООН П1 ошоею оопеио 00110001 оопоню оаи они аоо1опо аооиюп ООП1ООО аоо110о1 ОООПО1О оооо юп ааошоо аоаопо1 00001па ааааа Ш ппооп оооююо ООО1ОО1О ООО1ОООО ОООИЮО1 Шипа! пиона ошош шюш ооопооо оооо иио ОООО 2ОО1 оооопоо ааааа ни ооооопо ооооооп ПП 1001 ШПО1О оппоп ПППОО ОШПО1 апина ООШШ оооо нюо шпоп ааааа ив 00000010 Оааааааа ООООООО1 шша! Ш1ШО опшп шпш сделано для манж.!н$апайа.ого 7.2.! ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЬЕКТОВ 31 32 КОМБИНАТОРНЫЙ ПОИСК множестве (1,...,и) не может иметь больше М„элементов; шаблон рождественской елки предоставляет простое доказательство этой теоремы, поскольку ни один клаттер не может содержать более одного элемента из каждой строки.

На самом деле шаблоном рождестненской елки можно воспользоваться для того, чтобы показать существенно большее. Сначала замегим, что имеется ровно („")— — пй — 1 строк длиной и+ 1 — 2Й при 0 < Ь < и/2, поскольку в столбце й ровно Ц) элементов. Например, в табл. 4 имеется одна строка длиной 9, а именно нижняя; в ней также (э) — (э) = 7 строк длиной 7, (э) — (,) = 20 строк длиной 5, (з) — ( ) = = 28 строк длиной 3 и (э) — (э) = 14 строк единичной дчины, Кроме того, эти числа ("„) — („" ) появляются в треугольнике Каталани (22), поскольку они равны Сь(„ь) в соответствии с формулой (23).

Дальнейшее изучение показывает, что эта связь с числамя Каталана — не простое совпадение; ключом к более глубокому пониманию шаблона рождественской елки являются вложенные скобки, потому что теория скобок говорит нам, где в массиве располагается произвольная битовая строка. Предположим, что вместо 0 и 1 мы используем символы ( и ) соответственно. Любая строка скобок, вложенных или нет, может быть записана единственным способом в виде (37) (38) ) ( ( ) ) ( ) ) ( ) ) ) )( ( ( ( (( ) ( ( ) ( ) ( ( ( ) ), р = 5, д = 12, ао = е, а1 = (О) О, оз = О, аз = е ..., аш = ( О).

Б общем случае строка (37) представляет собой часть цепочки длиной д + 1, (39) ае)... а» 1)о»,»»е) ... о» з)»»» 1(с»»,...,с»е(п1... (с»», которая начинается с д свободных правых скобок ) и заменяет их по одной свободнымн левыми скобками (. Каждая строка шаблона рождественской елки получается точно таким способом, но с использованием 1 и О вместо ( и ); если цепочка а1... »г, соответствует строкам вложенных цепочек с»е,..., а, м то соответствующие цепочки (36) соответствуют строкам с»о, °,с»,-з,о»-з(о, 1) и ао, -,и -з,с -з,г» -ме.

(См. Снгт(з Огеепе апд Паше1 3. К1е(гшап, Х СошЬшагогш) ТЬеогу, А20 (1976), 80-88.) Обратите также внимание, что крайние справа элементы в каждой строке шаблона, такие, как 10101010, 10101011, 10101100,..., 11111110, 11111111 в случае и = 8, находятся в лексикографяческом порядке, Таким образом, например, 14 строк длиной 1 в табл.