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

Прочие использованные в атом выпуске обозначения можно найти в разделах "Основные обозначения" в ковце томов 1, 2 и 3. Естествеипо, аналогичный раздел будет и и томе 4. сделано для игал.1п$ши~а.ого Глава 7 Комбинаторный поиск Начальные разделы этой главы представлены в выпусках 0 н 1 тома 4, залла- Ф нированных к выпуску в 2006 н 200? году. 7.2 Генерация всех возможных обьектов 7.2.1 Генерация основных комбинвторных объектов В этом разделе рассматриваются методы обхода всех возможных объектов некоторого комбннаторного универсума, поскольку часто приходится сталкиваться с задачами, в которых необходим или желателен исчерпывающий перебор... 7.2.1.1 Генерация всех ть-кортежей Начнем с малого — рассмотрим, как получить все 2" строк из и бинарных цифр...

?.2.1.2 Генерация всех перестановок Следующей по важности после генерации кортежей из и элементов является задача генерации всех перестианоеок некоторого заданного множества или мульти- множества... Полностью тексты разделов У.2.1.1 н Т.2.1.2 можно найти в выпуске 2 тома 4. Ф 7.2.1.3 Генерация всех сочетаний Комбинаторика часто определяется как "изучение перестановок, сочетаний и т.п,'*, так что теперь обратим наше внимание на сочетания...

сделано для ьтьтичп$апаФа.огй 12 КОМБИНАТОРНЫЙ ПОИСК 7.2,1 7.2 1.4 Генерация всех разбиений Великолепная кинга Ричарда Стенли (ВбсЬап1 31ап1еу) Перечислитвльиая комбинаторика (Впшпегаг1те СотЬпшсонсв, 1986) начинается с рассмотрения ыдвенадцатнзадачия" — массива размером 2 х 2 х 3 фундаментальных комбинаторных задач, часто возникающих на практике... В предыдущих разделах данной главы мы рассмотрели п-кортежи, перестановки, сочетания и композиции... Таким образом, мы можем завершить наше изучение классической комбинаторной математики рассмотрением оставшихся пяти записей таблицы, которью включают разбиении (раг1111опэ)... Разбиения наново числа представляют собой способы записи его в виде суммы положительных целых чисел, независямо от их порядка... 7.2.1.5 Генерация всех разбиений множеств Перейдем теперь к рассмотрению другого вида разбиений.

Разбиения миоысесгпва представляют собой способы рассматривать множество как объединение непустых непересекающихся подмножеств... Полностью тексты разделов 7.2.1.3, 7.2.1А н 7.2.1.3 можно найти в выпуске 3 Ф тома 4, Поясните важность такой последовательности: ип, ооэ, ггеэ, диаиге, с1пс, нэ, ээг, ии(г, пои, оеи...~ — Ричард П, Стенли 1'Всйзгб Р. 5гап!еу), Перечислительиая комбинаторика (Епивега6ые СогпЬ1патопсэ) 11999) .. в едином тел» имеются пары члепов с одним и тем же именем, но различаемые кзк левые и правые...

— Сократ (5осгзгеэ), РЬаедпгэ 2ббд (ок. 370 г. до н.э.) 7.2.1.б Генерация всех деревьев К этому моменту мы уже завершили изучение классических концепций комбинаторики: кортежей, перестюювок, сочетаний н разбиений. Однако информатика внесла свой вклад, добавив еще один фундаментальный класс к традиционному репертуару, а именно иерархические конструкции, известные как деревья.

Деревья встречаются в информатике повсюду, как видно из раздела 2.3 и практически каждого из последующих разделов ХХскрссгпва програаьмпрованпл. Поэтому сейчас мы обратимся к изучению простых алгоритмов, с помощью которых можно исчерпыжюще исследовать деревья различного вида. Одын, дыэ„трн... (Фр.) сделано для игьеж$пйпата.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 13 Сначала давайте рассмотрим связь между вложенными скобками и лесом деревьев.

Например, строка 12 145 678 За Ь ги еГ ( ( ) ) ( ( ( ) ) ( ( ( ) ( ( ) ) ) ( ) ) ( ( ) ( ( ) ) ) ) 12 )4 з без зь ь сеь) содержит 15 левых скобок '(' с метками 1, 2, ..., 1 и 15 правых скобок ') ', также помеченных от 1 до 1. Серые линии под строками показывают, как соответствующие друг другу скобки образуют 15 пар 12, 21, 31, 44, 53, ба, 78, 85, 97, аб, Ь9, се, 4Ь, еа и 1с. Эта строка соответствует лесу узлами которого являются ф, ©, фф, ..., Я в прямом порядке обхода (отсортированные по первой координате) и Щ~, Я, (Щ, ..., ® в обратном порядке обхода (отсортированные по второй координате).

Если мы представим червяка, который проползает по краю леса (3) и видит, проползая по левой дуге узла, открывающую (левую) скобку '(', а по правой — закрывающую (правую) скобку ')", то его путь реконструирует исходную строку. В свою очередь, лес (2) соответствует бинарному дереву (4) сделано для ьтчтьтлп(апаса.ого 14 КОМБИНАТОРНЫЙ ПОИСК посредством "естественного соответствия", рассмотренного в разделе 2.3.2. Здесь список узлов в симл»строчная» порядке обхода — Е, ©, 9, ..., Е.

Левое поддерево узла Ох в бинарном дереве представляет собой крайнего левого потомка Я в лесу, или "внешний узел" П, если Ох не имеет потомюж. Правое поддерево х в бинарном дереве представляет собой правого 'брат" в лесу, или "внешияй узел" С), если Сх ) — крайний справа потомок своего родителя. Корни деревьев в лесу рассматриваются как братья, и крайняй слева корень в лесу является корнем бинарного дерева.

Строка скобок а1аз... аы имеет корректную вложенность тогда и только тогда, когда содержит п символов ' (' и и символов ') ', где Й-й символ ' (' предшествует Й-му символу ')' для 1 < Й < и. Простейший способ получить все строки вложенных скобок — посетить их в лексикографическом порядке. Далее приведен алгоритм, который рассматривает ') ' как лексикографически меньший символ по сравнению с '(' и включает некоторые усовершенствования для повышения эффективности по сравнению с оригинальным алгоритмом И.

Сембы (1. 8ешЪа) [ХпЕ Ргосеэапя Ьеггегз, 12 (1981), 188 — 192]. Алгоритм Р (Вложенные скобки в лексикографическом порядке). Для данного целого и > 2 алгоритм генерирует все строки азад... аз„вложенных скобок. Р1. (Инициализация.] Установить ать 1 — '(' и азь ~ — ') ' для 1 < я < и; установить также ае ~ — ') ' и т ~- 2п — 1. Р2.

(Посещение.] Посетить строку вложенных скобок а1аэ...аы. (В э»от момент а = '(' и аь = ')' для т < й < 2п.) Рй. (Простой случайу] Установить а,„- ')'. Затем, если а,„1 = ')', установить а 1 - '(', т ~- т — 1 и вернуться к шагу Р2. Р4. (Поиск Д Установить ) — т — 1 и й - 2п — 1. Пока а = '(', устанавливать а -')',аь — '(*,) -) — 1ий -к — 2.

Рб. (Увеличение а .] Завершить алгоритм, если ) = О. В противном случае установить а — '(', т — 2п — 1 и вернуться к шагу Р2. $ Позже мы увидим, что цикл на шаге Р4 почти всегда короткий: операция а - ')' выполняется в среднем только около з раза на одно посещение строки. 1 Почему работает алгоритм Ру Пусть А — последовательность всех строк о, содержащих р левых скобок и 9 > р правых (причем строка (д го обладает корректной вложенностью), перечисленных в лексикографическом порядке. Тогда алгоритм Р предназначен для генерации А„„, где, как легко видеть, А подчиняются рекурсивным правилам Агд — — ) Ар(д О, (А(р Од при О < р < а ф О; Аод = г", (5) кроме того, А пуста при р < О нлн р > а. Первым элементом А, является )д г()...

(), где имеется р пар 'О', последний элемент равен (г)д. Таким образом, процесс лексикографической генерации состоит из сканирования справа в поисках завершающей строки вида ау... аз„= ) ("+1)» и замене ее на () д+' г ()... О. Шаги сделано для»лг»лкпИанаса.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ ЕОМБИНАТОРНЫХ ОБ'ЬЕКТОБ 15 Таблица 1. Вложенные скобки и сопутствующие объекты прв и = 4 азаз...аз Лес Винврноедерево 4звзезез з1ззхззз р1рзрзр» сзсзсзсз Соответствие ПП 1357 1234 Е)00 П02 1356 1243 0001 У 0000 о(п(и 1О21 1З47 ° 1~ 1012 1346 Р4 и Р5 эффективно выполняют данную задачу, а шаг Рз предназначен для обработки простого случая р = О. В табл.

1 проиллюстрирован выход алгоритма Р при и = 4 вместе с соответствующими лесами и бинарными деревьями, как в случаях (2) и (4). В таблице приведено и несколько других эквивалентных комбинаторных объектов. Например, строка вложенных скобок может быть закодирована как о" о"...о"-, где неотрицательные целые числа з(зов... И„характеризуюттл ограничениями 4 + Из + " + А„< й для 1 < й < и; з(з + йз + " + 4, = и. (7) Вложенные скобки могут быть также представлены последовательностью зззз... з„, которая определяет индексы появлений левых скобок. Но сути, зззз... з„представляет собой одно из (з„") сочетаний и элементов из множества (1„2,..., 2п), отвечасделано для тзгиттЛВ$апаза.(зги 0(0) 0 о(оо) О((0)) (о) оо (ОПО) (оо)о (о о(н (о(он ((оно пони ((о он (((он) 1003 1345 02П 1257 1 ! „Ф 0202 1256 в ° ~Д.„ 0121 1247 з2 ~з) з ~" ОП2 1246 01Ы 12% 0031 1237 К 0022 1236 1 ~' оаз аи 0004 1234 1З24 ОО)О 1Ы ОО!1 ~.

1432 0012 2134 0100 2143 ОР31 2314 ОП О 2341 ОП1 Я 24З1 ОП 2 3214 0120 3241 0121 1 Ъ 3421 0122 4321 0123 а 16 КОМВИНАТОРНЫЙ ПОИСК юших определенным ограиичепиям хь 1<хь<2кдля1<к<ц, если считать, что ге = О. Разумеется, все з связаны с ш с(ь = хь+1 — хь — 1 для 1 < Й < и. (9) Алгоритм Р становится особенно простым, если переписать его лля геперации сочетаний з1зз... г„вместо строк а1аз... ая (см. упражнение 2). Строка скобок может быть также прецставлеиа перестановкой р1 рз... р„, где к-я правая скобка соответствует рь-й левой скобке; другими словами, к-й узел связанного леса в обратном порядке обхода является рь-и в прямом порядке обхода.