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

Например, лес (2) превращается в при нумерации его узлов в прямо-обратном порядке. Прямо-обратный н обратно-прямой порядки не просто курьез — они приносят реальную пользу. Это связано с тем, что соседние узлы при любом из этих порядков всегда находятся близко друг к другу в лесу. Например, узлы к и к + 1 являются смежными в (58) прн к = 1,4,6,8,10,13; онн радлелены только одним узлом при (с = 2,5, 7,9, 11 (если представить невидимый сверхродительский узел на вершине леса). Минутное размышление позволяет доказать по индукции, что между соседями как в прямо-обратном, так и в обратно-прямом порядке может располагаться не более двух узлов, поскольку обратно-прямой порядок всегда начинается с корня первого дерева илн его крайнего слева потомка, а прямо-обратный порядок всегда закаичиввегся корнем последнего дерева или его крайним справа потомком.

Предположим, что мы хотим сгенерировать все комбинаторные шаблоны некоторого вида и посетить их в порядке нююдобие кода Грея, так чтобы последовательные шаблоны всегда были "близки" друг к другу. Можно сформировать, по крайней мере концептуально, граф всех возможных шаблонов р с ребрами р — д для всех пар шаблонов, близких друг к другу.

Следующая теорема, открытая Миланом Секаниной (Мйап ВеЫпта) [Ярьэу РУ1пх(огИесйй галину Пшгегвйу г Вгпй, 1Чо. 412 (1960), 137-140), доказывает, что всегда возможен хороший код Грея, обеспечивающий получение одного шаблона нз другого при помощи последовательности коротких шагов. Теорема Я. Вершины любого связного графа могут быть перечислены в циклическом порядке (ее, щ,..., е„1), так что расстояние между сь и с<а+0 ~ „ле превышает 3 для 0 < й < и.

Доказатлельсшео. Необходимо найти остовное дерево графа н обойтн его в прямо- обратном порядке. 1 Ученые в области теории графов традиционно говорят, что Й-й степенью графа С является граф С~, вершины которого те же, что и у графа С, а ребро иуе присутствует в графе С тогда и только тогда, когда имеется путь длиной не более й между вершинами и н е в графе С. Это позволяет сформулировать теорему Я более кратко при п > 2: куб связного графа гамильтонов. Прямо-обратный обход полезен также в случае, когда мы хотим без циклов посетить узлы дерева при помощи ограниченного количества шагов. Алгоритм 44 (Прямо-обратный преемник в трижды связанном лесу). Если Р указывает на узел в лесу, представленном связямн РАВЕИТ, СНПЭ и 31В, соответствующими родителю каждого узла, его крайнему слева потомку и правому сделано для вувуъкпИанаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 45 брату, то данный алгоритм вычисляет узел й, следующий за Р в прямо-обратном порядке.

Предполагается, что известен уровень 1., на котором в лесу находится узел Р; значение 1. обновляется так, что указывает уровень узла й. Если Р— последний узел в прямо-обратном порядке, алгоритм устанавливает Я ~- Л и Ь вЂ” — 1. (41. [Прямой или обратный7] Если 1. четно, перейти к пшгу (44. (42. [Продолжение обратно-прямое.! Установить й - 318(Р). Перейтн к шагу (48, если й Р. Л. ь43.

[Перемещение вверх.] Установить Р РАВЕНТ(Р) и 1. — 1. — 1. Перейти к шагу ()7. (44. [Продолжение прямо-обратное.] Если СН1ЬР(Р) = Л, перейти к шагу (17. (Аб. [Перемещение вниз.) Установить й ~ — СН1ЬВ(Р) и Ь ~- Ь + 1. С[В. [Перемещение вниз при наличии возможности.] Если СНТЬВ(й) ~ Л, установить й - СНТЬВ(й) и Ь - Ь+ 1. Завершить работу алгоритма. (47. [Перемещение вправо илн вверх.[ Если 318(Р) ф Л, установить й - 318(Р)", в противном случае установить й — РАВЕНТ(Р) и 1.

— Ь вЂ” 1. Завершить работу алгоритма. ! Заметим, что, как и в алгоритме 2.4С, связь РАНЕНТ(Р) проверяется, только если 31В(Р) = Л. Полный обход представляет собой путешествие червя вокруг леса, наподобие (3): червь "видит" узлы на четных уровнях прн проходе слева, а на нечетных — при проходе справа. Упражнения 1. [1о] Каким образом реконструировать строку скобок (1) при проползании червя цо бинарному дереву (4)7 2. [80] (Ш. Закс (8. Еа)гв), 1980.) МодиФицируйте алгоритм Р таким образом, чтобы он выдавал сочетания х~гз...

з„из (8) вместо строк скобок а1от... аз„. ь 3. [ЕУ] Докажите, что (11) преобразует с1 зт... г„в таблицу инверсий с1 сз... с„. 4. [80] Истинно или ложно утверждение: если строки а1... аз„сгенернрованы в лексикографическом порядке, то в том же порядке находятся строки 41... 4„, з1... с„, р| ° ри и с1 ° сч. б, [10] Какие таблицы 41... д„, а1... з„, р1 ...Р„и с1... с, соответствуют строке вложенных скобок (1) 7 ~ 6. [00] Какое соошоешсшоие (см. последний столбец табл. 1) сопоставляется строке (1)7 7.

[10] а) В каком состоянии находится строка а1аз... аз„при завершении работы алгоритма Р7 сделано для мчинлп(апаТа.ого 46 КОМБИНАТОРНЫЙ ПОИСК о) Что содержится в массивах 111з... 1„и г1гт... г„при завершении работы алгоритма В? 8. [1в) Как выглядят таблицы 11... 1„, г1 ... г„, е1 ... е„и в1... и„, соответствующие лесу [2)? 9. [МЯО) Покажите, что таблицы с1... с„и в1... в„связаны соотношением сь = [в1 > й — 1) + [вз > й — 2) + . + [вь 1 > 1) .

10. [МОО) (Обход червя.) Для заданной строки си аз... аз„обозначим через ю превышение количества левых Скобок нвд правыми в подстроке а1аз... аз, 0 <,? < 2п. Докажите, что юе+ ю1 + ° ° + ют„= 2 [С1 + ° ° + с„) + и. 11. [11) Если Р— некоторый лес, сопрлясеннмй лес Р получается путем зеркаль- ного отражения слева направо.

Например, для 14 лесов нз табл. 1 сопряжениымн яВляются 1", 1', *', ~, "1, 11, 'Л, Фь, ~ь [солексные леса из табл. 2), Если Р соответствует некоторой строке вложенных скобок а1аз... ат„, то какой стРоке соответствУет Рл? 12. [14) Если Р— некоторый лес, трвнспвнирвваннмй лес Рг получается путем обмена в каждом бинарном дереве леса Р левых н правых связей. Например, для 14 лесов из табл. 1 транспонированнымн являются Что дает транспоннрование леса [2)? 13. [ЗО] Продолжая упражнения 11 н 12, как соотносятся прямой и обратный порядок обхода помеченного леса Р и прямой и обратный порядок обхода [а) РЯ; [) ) Ртт ю 14. [Я1) Найдите все помеченные леса Р, такие, что Рлт = Ртл.

1$. [ОО) Предположим, что  — бинарное дерево, полученное из леса Р путем связи каждого узла со своим левым братом и крайним справа потомком, как в упражнении 2.3.2-5 и последнем столбце табл. 2. Пусть Р' — лес, естественным образом соответствующий В, посредством связей с левым потомком и правым братом. Докажите, что Р' = Р~~ [с ипюльзованием обозначений из упражнений 11 и 12).

16. [ОО) Пусть Р н С вЂ” леса, а РС означает лес, полученный путем размещения деревьев Р слева от деревьев С; кроме того, определим Р ) С = [СТРТ) . Приведите интуитивное объяснение оператора ) и докажите, что он ассоциативен. сделано для ьтттьнлн$анага.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 47 17.

[М46] Охарактеризуйте все непомеченные леса Р, такие, что глт = гтл (см. упражнение 14). 18. [Уд] Два леса называются редсшееннь»ми (сокпасе), если один из них может быть получен из другого при помощи некоторого количества операций получения сопряженного леса и/или транспонирования. Примеры в упражнениях 11 и 12 показывают, что каждый лес из четырех узлов принадлежит одному из трех классов родственности: ~ ° ° » м [;11 = ' 1 = 1 *' = 1 = 1 = „ф Изучите множество всех лесов из 15 узлов. Сколько классов зквивелентности родственных лесов они образуют? Какой класс наибольший? Какой класс наименьший? Чему равен размер класса, содержащего (2)? 10.

[38] Пусть Рм Гю..., Рл — последовательность непомеченных лесов, соответствующих вложенным скобкам, сгенерированным алгоритмом Р, и пусть См Сш..., См — последовательность непомеченных лесов, соответствующих бинарным деревьям, генерируемым алгоритмом В. Докажите, что С» = Р»~~ (с использованием обозначений из упражнений 11 и 12). (Лес Рл™ называется дральнмм к лесу Р и далее в ряде упражнений обозначается как г и.) 20.

[33] Вспомним из раздела 2.3, что стененые узла в дереве называется количество его дочерних узлов и что расширенное (ехсепдес() бинарное дерево характеризуется тем свойством, что каждый его узел имеет степень либо О, либо 2. В расширенном бинарном дереве (4) последовательность степеней узлов в прямом порядке обхода представляет собой 2200222002220220002002202200000; зта строка нулей и двоек идентична последовательности скобок (1), с тем отличием, что каждая скобка Ч' заменяется двойкой, каждая скобка Ч ' — нулем, а также добавляется дополнительный ноль.

а) Докажите, что последовательность неотрицательных целых чисел 616»...Ьл представляет собой последовательность степеней леса в прямом порядке обхода тогда н только тогда, когда оиа удовлетворяет следующему свойству для 1<6<%: 6|+ 6»+ + Ь»+ у > 6 тогда и только тогда, когда 6 < Ф. Здесь 1 = Х вЂ” 61 — Ьз — ° — Ьл — количество деревьев в лесу.