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

(26) Количество листьев ниже узла ® в згом дереве рекурсии равно Срэ, а узел ® встречается ровно С(„д)(„1 р) раз на уровне и — 1 — р; таким образом, мы должны получить С(„эК„1 р)Срд — — С„дли О < Р < и. (27) Четырнадцать листьев (25) слева направо соответствуют четырнадцати строкам табл. 1 сверху вниз. Заметим, что элементы столбца с1сзсэс4 в этой таблице назначают соответствующие числа 0000, 0001, 0010, ..., 0123 листьям дерева (25) в соответствии с "десятичной записью Дьюи" для узлов дерева (но с индексами, начинающимися с О, а не с 1, и с дополнительным 0 в начале).

Червяк, который ползет от одного листа к следующему по низу дерева рекурсии, будет подниматься и опускаться на Ь уровней при изменении Ь координат с|... с„, те. когда алгоритм Р сбрасывает значения Ь '(' и Ь ') '. Это наблюдение облегчает понимание предыдущего вывода о том, что условие Ь > х вьпюлняется ровно С„ рэз в процессе движения червяка. Еще один способ понимания алгоритма Р возникает при рассмотрении бесконечного ориентированного графа, определяемого рекурсией (21): Очевидно, что Ср — количество путей от фф~ к ЩО в этом ориентированном графе в силу (21). И действительно, каждая строка скобок Арч непосредственно соответствует такому пути, где '(' означает шаг влево, а ')' — шаг вверх.

Алгоритм Р сделано для ькэкьилп$ппц(а.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 25 систематически исследует все такие пути, пытаясь сначала перейти вверх при продолжении частичного пути. Таким обрезом, легко определить М-ю строку вложенных скобок, посещаемую алгоритмом Р,начиная с узла (йп) и выполняя сведующие вычисления, находясь в узле Я» если р = д = О, завершить работу; в противном случае, если Ф < Ср( вывестй) ', установить 9 - д — 1 и продолжить работу; в противном случае установить Ж вЂ” Х вЂ” Ср1 О, вывести '(', установить р — р-1 и продолжить выполнение. Приведенный далее алгоритм [г?ап(г Ипв)геу, РЬ.!). споры (1)п1чегв(су о! Сашогп(а аФ Бап !)1ейо, 1978), 16-24[ избегает предвычнслення треугольника Каталана путем вычисления Срч "на ходу".

Алгоритм Ю (Неранжироваиная строка вложенных скобок), Для заданных и и Ф, где 1 < )т" < С, алгоритм вычисляет )У-й вьпюд алгоритма Р. Ш. [Инициализация.[ Установнтыу ~ — и и п1 — р — е — 1, Пока р < и, устанавливать р ~- р + 1 и с - ((4р — 2) с)/(р + 1), П2. [Выполнено?[ Завершить работу алгоритма, если 9 = О.

!13. [Вверху] Установить с' — ((д+ 1) (9 — р) с)Яд+ р) (9 — р+ 1)). (В этот момент мы и~сам 1 <«)т' » «с = Ср, н с' = Ср~д Н.) Если )т' «< с', установить 9 +- ~7 — 1, с — с', а,„~ — ') ', т — т+ 1 и вернуться к шагу 112. !)4. [Влево7[ Установить р — р — 1, е - с — е', г7 - Ж вЂ” с', а,„~- '(', т ~- т+ 1 и вернуться к шагу 113. ! Случайные деревья. Строку вложенных скобок а1аз... аэ„можно получить случайным образом, просто применяя алгоритм 11 к случайному целому числу )У между 1 и С„.

Однако эта идеи не слишком хороша при и, превышшощем 32 или около того„поскольку С„может быть очень болыпим. Более простой способ, предложенный Д.Б. Арнольдом (1).В. АгпоМ) и М.Р. Слином (М.И. $1еер) [АСМ Т?апв. Ргоя. Ьалйпа8ел аад БурГешв, 2 (1980), 122-128[ заключается в генерации случайного "путешествия червя"', начиная с узла Я) в графе (28) и выполняя ветвления влево илн вверх с соответствующими вероятностямн. Полученный алгоритм практически такой же, как и алгоритм П, но работает только с неотрицательными положительными целыми числами, меньшими п~ + п + 1. Алгоритм %' (Равномерно распределенные случайные строки вложенных скобок). Этот алгоритм генерирует случайную строку а1аэ...

аэ„корректно вложенных скобок. 'Ж1. [Инициализация.[ Установить р ~ — 9 — п и т — 1. '6~3. [Выполненоу[ Завершить работу алгоритма, если а = О. %г3. [Вверху[ Пусть Х вЂ” случайное целое число в дивлвзоне 0 < Х < (9+ р) (д— — р+ 1). Если Х < (9+ 1) (д — р), установить 4 — д — 1, а,„— ') ', т — т+ 1 и вернутьея к шагу %2. Ж4.

[Влево.[ Уетановкть р — р — 1, а — '(', т — т + 1 и вернутьсл к шагу %3. ! сделано для ькьлк! н)апаса.ого 26 КОМВИНАТОРНЫЙ ПОИСК 7.2.1 Маршрут червя можно рассматривать как последовательность юеюг... ю2„, где ю — текущая глубина червя после т шагов. Таким образом, юо = О; ш = ю г+ +1,еслиа ='(,ии =ю ~ — 1,еслиа =')';мытакжеимеемш >О, шт„= О.

Последовательиость шею1 ... юзе, соответствующая (1) и (2), представляет собой 0121012321234345432321232343210. На шаге %3 алгоритма % мы имеем д + + р = 2п + 1 — т и д — р = ю,ч г. Назовем коитррам (оисйпе) леса путь, который проходит через точки (т, — ш ) иа плоскости (О < т < 2и), где шею1 ...юз„— маршрут червя, соответствующий связанной строке а1... аз„вложеяиых скобок. На рис. 36 показано, что будет, если мы изобразим контуры всех 50-узловых лесов, причем степень затенения каждой точки соответствует количеству лесов, лежащих нэд ией.

Например, ш1 всегда 1, так что треугольная область вверху слева иа рис. 36 имеет максимально черный цвет; шз может принимать значения 0 либо 2, причем 0 встречается в С4э Сео/4 случаях; соответственно ромбовидиал область затенена иа 75%. Таким образом, рис. 36 иллюстрирует форму случайного леса, аналогичную формам случайных разбиений, с которыми мы встречались иа рис. 30, 31 и 35 в разделах 7.2.1.4 и 7.2.1.5. Рис. 36. Форма случайного 50-узлового леса Конечно, в действительности мы ие в состоянии изобразить контуры всех этих лесов, поскольку общее их количество равно Сео = 1 978 261 657 756 160 653623 774 456.

Но при помощи математики можно имитировать такое действие. Вероятиость того, что ют = 2й раева С1 ья,„+ь1С1„„, ьн„+ь>/С„, поскольку имеется С1„, ьц, +ь1 способов начать с т + й левых скобок и т — й пРавых скобок и С~„-„, ьл„-„+ь1 способов закончить и — (т + й) левыми скобками и и — (т — й) правыми скобками. С использоваиием формулы (23) и приближения Стирлиига получаем, что эта вероятность равна 1 2 (т+й+1)(и — т+й+1) т — й и — т+й п (2й+ 1) — 2два-в1 1 1+ О й+ 1 + О й (29) где т = ди и и -~ оо, при О < д < 1. Среднее значение шт выводится в упражиеиии 57; оио равно (4т(п — т)+и)( )( „" ~) 6(1 — 9)п 2в 1 1+О1и и показано па рис.

36 в виде кривой для и = 50. Когда п велико, маршрут червя приближается к так называемому броуиовскому движению, представляющему собой важную концепцию в теории вероятностей. сделано для мгэик! пГапаса,ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЬЕКТОВ 27 Рис. 37. Положения внутренних узлов в случайном 50-узловом бинарном дереве Как и на рис.

36, гладкие кривые на рис. 37 и 38 показывают среднюю глубину узла; точные формулы выводятся в упражнениях 58 и 59. Асимптотическн средняя глубина внешнего узла т равна 9(1 — 9)п / 1 1 8 — 1+ 0 1 — ) при т = рп и п — оо к ~ /и) (31) для всех фиксированных отношений 0 < д ( 1, что удивительно похоже на формулу (30); средняя глубина вмргаремнего узла га асимптотически та же, но ' — 1' заменяется на '-3'.

Таким образом мы можем сказать, что в срацнем форма бинар- сделано для мгьввулп1апаФа.ого [См., например, Рап1 Ъ йгу, Ргосеввив Всосйввнцпев е1 Моигетепг Вговтиеп (1948), 225-237; Спу 1опсйахб, .7. Арр!юс) РгоЬ, 21 (1984), 479-499, н В1Т, 26 (1986), 17-34; ВачМ А1бопв, Е!есггоо$с Соттшисанопв ш РгоЬабйяу, 3 (1998), 79-90; Лоп %штеп, Е!естюшс Соттишсанопв Ь1 РгоЬаЫЬау, 4 (1999), 25-29; д.-р. Мвхскегс, Влпс)ош БвгисФигев апд А)догййпм, 24 (2004), 118-132.) Какой внд имеет случайное бпнармое дерево? Этот вопрос был исследован Франком Раскн (г1апк Вцв)геу) 1о1АМ,7.

А)8еЬгшс апс) Вйвсгехе МесЛос)в, 1 (1980), 43-50], и ответ на него достаточно интересен. Предположим, что мы изобразили бинарное дерево как в 14), с т-м внутренним узлом в горизонтальной позиции т, где узлы пронумерованы в симметричном порядке. Если изобразить все 50-узловые бинарные деревья таким образом и наложить нх одно на другое, то мы получим распределение положений узлов, показанное на рис. 37.

Аналогично, если мы пронумеруем емеюмие узлы ст О до и в симметричном порядке и разместим их в горизонтальных позициях .5, 1.5,..., и+.5, то "бахрома" от всех 50-узловых деревьев образует распределение, показанное на рис. 38. Обратите внимание, что корневой узел с наибольшей вероятностью имеет номер 1 нли и, становясь крайним справа или слева; менее всего вероятно, что он находится посередине, в позициях 1(п+ 1)/2) или Ип+ 1)/21. 28 КОМБИНАТОРНЫЙ ПОИСК в!$йнняап" '"'. йв! нййянайппаФ.":-,.вФ!чмп4!; ам 5 ч'!-:5~МВВ%ймймФюйм мж',: ".ннщ няяяяяаяпмнгнчп'еммуваа~мйтмтмпамяяяннафф щяв емяй янаампмпямйманплймнпмапайпмянащ Ймп-. Рис.

38. Положения внешних узлов в случайном 50-узловом бинарном дереве ного дерева приближенно представляет собой нижнюю половину эллипса шириной и елнннц и глубиной 4т/и/т уровней. Три других заслуживаюпшх упоминания способа генерации случайных закодированных лесов рассматриваются в упражнениях 60-62. Они менее непосредственны, чем алгоритм %, но представляют собой значительный комбинаторный интерес. Первый начинается с произвольной случайной строки, содержащей и левых и и правых скобок, не обязательно вложенных; каждая из ( „") возможных строк равновероятна. Затем строка обрабатывается для преобразования в корректно вложенную последовательность таким образом, что каждому окончательному варианту соответствуют ровно и + 1 исходных строк.

Второй метод аналогичен, но начинается с последовательности и+ 1 нулей и и двоек, отображая их таким образом, что к каждому конечному результату приводят ровно 2и + 1 исходных строк. Третий метод дает каждый конечный результат ровно из и битовых строк, содержащих и — 1 единиц и и + 1 нулей. Другими словами, эти три метода предоставляют комбинаторное доказательство того, что С„одновременно равно (~) / (и+ 1), ( "„+') / (2и+ 1) и („~",) / и. Например, при и = 4 мы получаем 14 = 70/5 = 126/9 = 56/4, Если мы хотим сгенерировать случайные бинарные деревья непосредственно в сввзанном виде, можно воспользоваться красивым методом, предложенным Ж.-Л. Реми (1.Ь.

Н4шу) [11АШО 1пГогтаядие ТЬ4ог!дие, 19 (1985), 179-195). Его подход особенно поучителен, поскольку показывает, как случайные деревья Ката- лана могут возникнуть "в природе", с использованием удивительно простого механизма„основанного на классической идее Олинде Родригеса (О!!пбе Вабпйпеэ) (Х пе МаГй, 3 (1838), 549). Предположим, что наша цель — получение не только обычного и-узлового бинарного дерева, но и декорированного (десога!е3), т.е. расширенного бинарного дерева, в котором внешние узлы помечены числами от 0 до и в некотором порядке. Всего имеется (и + 1)! способов декорировать любое данное бинарное дерево; таким образом, общее количество декорированных бинарных деревьев с и сделано для ьрькькпИанаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОь1БИНАТОРНЫХ ОБЪЕКТОВ 29 внутренними узлами составляет ХУ„= (а + 1)!С„= —, = (4а — 2) ХУь ь (2а)! а! (32) Реми обнаружил, что существует 4а — 2 простых пути построения декорированного дерева порядка а из данного декорированного дерева порядка а — 1: мы просто выбираем любой узел из 2а — 1 узлов (внутренних или внешних) в данном дереве, например узел х, и заменяем его либо, либо таким образом вставляя новый внутренний узел н новый лист, перемещал х и его потомков (если таковые имеются) на один уровень вниз.

Например, вот один из вариантов построения декорированного дерева порядка 6: Алгоритм К (Раступхее случайное бинарное дерева). Данный алгоритм кон- струирует представление с использованием связей Х еЬ1... ьзм (с указанными выше соглюпениями) равномерно распределенного случайного бинарного дерева с Ф внут- ренними узлами, К1. [Инициализация.[ Установить а — О и Ьо - О.