Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 18
Текст из файла (страница 18)
Земля является противоположностью воздуху, а огонь — воде. Этим завершается анализ с использованием треугольника (В, С,:0), Переходя к треугольнику (Е, Е, С), Луллий замечает, что разные процессы в природе начинаются при доминировании одного элемента над другим; затем выполняется переход, или среднее состояние„после чего достигается конечное состояние, например воздух становится горячим, По поводу треугольника (Н, 1, К) Луллий говорит, что в общем случае огонь > воздух > вода > земля в плане нх "сфер", "'скоростей" и "знатности*', тем не менее мы также имеем, например, воздух > огонь по отношению к поддержанию жизни, а при совместной работе воздух и огонь равны. На рис. 45 справа приведена представленная Луллием вертикальная таблица, смысл которой станет понятен из упражнения 11.
Он также разработал подвижные концентрические колеса, помеченные буквами (В,С,В,Е,Р,С,Н,1,К) и другими именами, что позволило ему работать со многими разнообразными типами элементов одновременно. Работая таким способом, верный последователь Луллия мог быть уверен, что рассматривает все возможные случаи. (Луллий мог видеть подобные колеса в ближайшей еврейской общине; см. М. 1де1, 7.
Игагбигй алд Сопгсап16 1пэй1п1ее, 51 (1988), 170-174, а также вклейки 16-17.] Несколькими столетиями позже Атанасиус Кирхер (АсЬапэв1пв К1гсЬег) опубликовал развитие системы Луллия как часть большою тома, озаглавленного Агэ Майна Ясюпй' Иге СошЫпа~ог(а (АшэСегдаш, 1669), в котором на с. 173 имелось пять подвижных колес. Кирхер также расширил множество используемых Луллием полных графов К„, приведя иллюстрации полных дердольнмз графов К,„; например, рнс. 46 взят со с. 171 книги Кирхера; на с.
170 той же книги показан граф Кгвлв. Рис. 46. Граф Ккм опублико- ванный Кнрхером в 1669 голу сделано для эуълкиИанаса.ого 80 КОМБИНЛТОРНЫЙ ПОИСК Это искусство исследовать и изобретать. Когда идеи комбинируютсл всеми возможными способами, новые комбинации открывают новые пути для размышлений и приводят к открытию новых истин и аргументов. — Мартин Гарднер (Магбп багсгпег), Логические машины и диаграммы (Еорс МасЫпез аеУ 07айгатз) (1956) Наиболее далеко идущим современным развитием методов в духе Луллия, вероятно, является работа Иосифа Шиллингера (ЛоеерЬ БсЫ01пйег) ТЬе Бс)йЛшяег Яувсеш оЕМив1са) Сотпровнюл (Хек Уогй: Саг1 г 1всЬег„1946), замечательный двухтомник, рассматривающий теории ритма, мелодии, гармонии, контрапунктов, композиции, оркестровки и прочего с точки зрения комбинаторики.
Например, на с. 56 Шиллингер перечисляет 24 перестановки (а, Ь, с, 4) в порядке кода Грея (алгоритм 7.2.1.2Р); на с. 57 он применяет их не к мелодии, а к ритму, к длительности нот; на с. 364 он приводит симметричный цикл (Гй) (2,0,3,4,2,5,6,4,0,1,6,2,3,1,4,5,3,6,0,5,1), универсальный цикл 2-сочетаний для семи объектов ~0, 1, 2, 3, 4,5,6); другими словами, (13) представляет собой зйлеров путь в Кт: все ( ) = 21 пар цифр встречаются ровно по одному разу. Такие шаблоны — настоящая золотоносная жила композитора, но мы должны быть благодарны, что лучшие ученики Шиллингера (наподобие Джорджа Гершвина (беогйе бегеЬкчп)) все же не ограничились строго математическим восприятием зстетики. Тако, ван Шутем и Изкуврдо, В 1650-х годах были опубликованы еще три книги, связанные с рассматриваемой нами темой. Андре Тако (Апг)ге Тасцпес) написал общедоступную книгу АИ11ипенсм ТЬеопа е1 Ргахи (1оптшп, 1656), которая перепечатывалась н исправлялась в течение следующих 50 лет.
В конце книги (с. 376 н 377) он привел процедуру для перечисления сочетаний по два, по трн н т.д. Книга Франца ван Шутена (ггапв тап ВсЬоосеп) Ехегс1гаяопев Маайешансш (1 е1- деп, 1657) была более серьезной. На с. 373 в ней перечислены все сочетания в виде привлекательной схемы с. ас. Ьс. аЬс н следующие несколько страниц посвящены расширению данного шаблона при вве. денни букв е, 7", о, Ь, 1, Ь "и так до бесконечности". На с. 376 автор замечает, что в выражении (14) можно заменить (а, Ь,с,4) на (2,3,5,7) и получить делители 210, превышающие единяцу.
2 3 6 (15) 71 14235 15 1 сделано для имжшГанаса,ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЬЕКТОВ 81 На следующей странице начальная идея распространяется на а а. аа (16) с. ас. аас. Ьс. аЬс. ааЬс таким образом позволяя иметь две буквы а. Тем не менее в действительности автор не понял это расширение; его следующий пример (17) Ь.
аЬ, ааЬ. аааЬ Ь. ЬЬ, аЬЬ. ааЬЬ. аааЬЬ выполнен неверно, указывая границы знаний того времени (см. упражнение 13). На с. 411 ван Шутен заметил, что веса (а, Ь, с, Ы) = (1,2, 4,8) в (14) при использовании сложения дают 1 2 3 (18) 8 9 10 11 12 13 1 15 Однако он не увидел здесь связи с двоичными числами. Двухтомник Себастьяна Изкуэрдо (ЕеЬазсьйп 1ж1шеп1о) РЬагив Бс!епяагит (1 уоп, 1659) — "Маяк науки" — включает в себя хорошо организованное обсуждение комбинаторики под заглавием В(зрисано 29, 11е СотЬшанопе. Автор приводит детальное обсуждение четырех ключевых частей "двенадцатизадачия" Стенли, а именно п-кортежей, п-размещений, ц-мультнсочетаний и и-сочетаний нз т объектов, которые находятся в первых двух строках и двух столбцах табл. 7.2.1.4-1, В разделах 81 — 84 Ое СотЬшанопе автор перечисляет (в лексикографическом порядке) все сочетания из т букв по и, для 2 < и < 5 н п ~ т < 9; он также протабулировал их для ш = 10 и 20, при п = 2 и 3.
Однако при перечислении шп 1мамещений ш элементов по и он использовал более сложный порядок (см, упражнение 14). Изкуэрдо был первым, кто открыл формулу ( +„" ') для сочетаний т элементов по и с неограниченными повторениями; это правило встречается в 3 48-51 его книги. Однако в 3 105, когда он пытается перечислить все такие сочетания при и = 3, он не знает, что существует простой способ сделать это. Фактически его перечисление 56 случаев для т = 6 больше напоминает старый запутанный порядок (12). Сочетания с повторениями не были хорошо поняты до тех пор, пока в 1713 году не вышла книга Якоба Бернулли (.1ашев ВегпонП1) Агв Сощесгапей (" Искусство догадки"). В части 2, главе 5 Бернулли просто перечислил все возможности в лексикографическом порядке н показал, что формула ( "„" ') является простым следствием применения индукции.
(Николо Тарталья (%ссо)Ь ТагтайЬа), кстати„близко подошел к получению этой формулы в своей книге Сепега1 1гана1о й питеп', еС т1зиге, 2 (Уешсе, 1556), 17' и 69"; то же справедливо и в отношении магрибского математика Ибн Мунима (1Ьп Мип'1ш) и ехо книги Ещй а1-.(йваЬ, написанной в Х1П веке.) сделано для втвцичп(апаса.ого 82 КОМВИНАТОРНЫЙ ПОИСК Нулевой случай. Перед тем как завершить наше рассмотрение ранних работ по сочетаниям, следует не забыть небольшой, но важный шаг, сделанный Джоном Уоллисом (доЬп%айз) в книге Вйзсопгэеог" СошЬшаг)опз (1685), где нас. 110 он, в частности, рассматривает сочетание 0 объектов из гл элементов: "очевидно, что, когда мы выбираем Ничпю, то мы осшаеллсм Все.
Это можно сделать только одним способом, сколько бы объектов у нас ни было". Кроме того, на с. 113 ои утверждает, что (с) = 1: "в этом случае выбрать все или оставить все — это одно и то же". Однако, приводя таблицу факториэлов п! для и < 24, он не зашел так далеко, чтобы указать, что О! = 1 или что имеется ровно одна перестановка пустого множества. Работа Нараяны.
Замечательная монография Сэп1га Капший ("Наслаждение лотосом вычислений" ), написанная Нараяной Пандита (Нагауапа Рапбйа) в 1356 году, стала не так давно известна за пределами Индии благодаря переводу на английский язык Пармаяаидом Сингхом (Рагшэпэлб ВшйЬ) [Сатлга ВЬага17, 20 (1998), 25-82„21 (1999), 10-73; 22 (2000), 19-85; 23 (2001) 18-82; 24 (2002) 35 — 98)„см. также диссертацию Такзлори Кусуба (Тайэлоп' КпзпЬа) из Вгони Пшэегэ($у (1993). Глава 13 книги Нараяны, озаглавленная Апйа Раба (" Соединение чисел"), посвящена комбинаторной генерации.
Хотя 97 "сутр" этой главы достаточно загадочны, они содержат полную теорию, опередившую мировую науку в этой области иа несколько столетий. Например, Нараяна описывает генерацию перестановок в сутрах 49-55а, где приводит алгоритм для перечисления всех перестановок множества в уменьшающемся солексном порядке, приводя при этом способ вычисления ранга данной перестановки н восстановления перестановки по рангу.
Эти алгоритмы появились более чем за столетие до этого в известной работе Сарнгадевы (8агпйадега) Яалйтгагагпайага (" Добыча жемчуга музыки"), 3 1.4.60-71. Таким образом, Сарнгадева, по сути, открыл факториэльиое представление положительных чисел. В сутрах 57-60 Нарвала развил алгоритмы Сарнгвдевы так, что можно было легко переставлять мульти- множества общего вида; например, он перечисляет перестановки мультнмножества (1,1,2,4) в обратном солексном порядке: 1124,1214,2114,1142,1412,4112,1241,2141,1421,4121,2411,4211.
В сутрах 88-92 Нараяна занимается систематической генерацией сочетаний. Помимо иллюстрации 3-сочетаний множества (1,..., 8), а именно (678, 587, 478,..., 134, 124, 123), он также рассматривает представление этих сочетаний в виде битовых строк в обратном порядке (еозрасшаюп1пй солексный порядок), тем самым развив метод Бхаттотпэлы (ВЬа1)оСра)а), разработанный в Х веке: (11100000, 11010000, 10110000,..., 00010011, 00001011, 00000111) . Он почти — но не до конца — открыл теорему 7.2.1,3Ь. Перестаионочная поэзии. Обратимся теперь к одному занимательному вопросу, привлекавшему внимание ряда видных математиков в ХЪ'П веке; зто прольет свет сделано для ьуэуькиИапаса.огя 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 83 на состояние комбинаторных знаний в Европе того времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
