Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 16
Текст из файла (страница 16)
В действительности, как поясняется в книге Найлана (с. 28), Янг разработал простой способ для вычисления ранга каждой тетраграммы, как если бы он пользовался троичной системой счисления. Таким образом, нас не должно удивлять упорядочение бинарных гексаграмм Шао Юнгом, хотя он и жил более чем на 1000 лет раньше. Индийская поэзии. Бинарные кортежи из п элементов изучались в совершенно ином контексте мудрецами в древней Индии, посвятившими себя священным ведическим песнопениям. Слоги в санскрите либо короткие (!), либо длинные (3), а нзучепие шаблонов слогов называется просодией (рговобу). Современные писатели вместо символов ! и 3 используют символы и —.
Типичная ведическая строфа состоит из четырех строк с и слогами в строке, для некоторого и > 8. Таким образом, нужен способ классифицировать все 2" возможных шаблонов. Классическая работа Пингалы (Р!пйа!а) Чандасутра (СЬапдаЬ4авсга), написанная до 400 года н. э. (вероятно, существенно ранее — точная датировка неизвестна), описывает процедуру поиска индекса Й любого заданного шаблона, состоящего из н —, а также поиск шаблона для заданного значения /с. Другими словами, Пингала поясняет, как найти раяв данного шаблона и как найти шаблон по заданному рангу. Таким об- СДЕЛаНО ДЛЯ 1ВгЬЛКПИаааФа.ОГЕ 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 69 разом, он зашел в своих исследованиях дальше Янг Цинга (Уапй Нэ1ппй), который рассматривал только задачу поиска ранга, но не шаблона по заданному рангу, Методы Пингвлы также связаны с возведением в степень, как мы видели ранее в связи с алгоритмом 4,6.3А. Следующий важный 1паг был сделан просодистом Кедарой (Кег)вга) в его книге 1'1тгагаэпайага, которая, как считают, была написана в ЧП1 веке.
Кедара пошагово описал процедуру для перечисления всех п кортежей от —... — к— ...— к —...— к — — ...— к — ...— к ...к —... т.е. по сути алго- '5 ритм 7.2.1ЛМ для основания системы счисления„равного 2. Его метод можно считать первым явным алгоритмом для генерации комбинаторной последовательности. (См.
В. гап апогея,,у. 1шйап Р)нТоэ., 21 (1993), 31-50.] Стихотворные измерения можно также рассматривать как ритмы, с одним тактом для каждого и с двумя для каждого —. Хотя и-тактовый шаблон может включать от и до 2п тактов, музыкальные ритмы для маршей или танцев обычно основаны на фиксированном количестве тактов. Следовательно, естественно рассматривать множество всех последовательностей и —, содержащих фиксированное значение пг тактов. Такие последовательности называются последовательностями кода Морзе (Могэе) длины т, и из упражнения 4.5.3-32 известно, что их ровно Г +ь Например, 21 последовательность для т = 7 имеет вид (2) Таким образом, индийские просоднсты пришли к открытию последовательности Фибоначчи, как уже отмечалось в разделе 1.2.8.
Кроме того, анонимный автор Ргай71а Рашяа)а (около 1320 года) разработал элегантный алгоритм для определения ранга ритма и восстановления ритма по рангу для т-тактовых ритмов. Для поиска Й-го шаблона начинаем с записи гп символов , затем выражаем разность И = Г т1 — Й как сумму чисел Фибоначчи Гу, +- ° . + Е~,; здесь Г, — наибольшее число Фибоиаччи, не превышающее г(, Гя — наибольшее число Фибоначчи, не превышающее и' — Г.„и так до тех пор, пока не будет получен нулевой остаток. Тогда такты ( — 1 и у заменяются с на — для 7' = 7м...,Я. Например, для получения пятого элемента последовательности (2) мы вычисляем 21 — 5 = 16 = 13+ 3 = Гг + Г4; ответом является Несколькими годами позже Нарвина Пандита (Нагауапа Раис)на) рассматривал более общую задачу поиска всех композиций т, части которых не превышают д, где д — любое данное положительное целое число.
Как следствие, он открыл последовательности Фнбоначчи 9-го порядка 5.4.2-(4), которые пригодились через 600 лет после этого в многофазной сортировке; он также открыл соответствующие алгоритмы определения ранга и элемента по заданному рангу. (См. Рагшапапд 81пйп, Нм1она Магйешанса, 12 (1985), 229-244, а также упражнение 16.) сделано для волк! ананаса.ого 70 КОМБИНАТОРНЫЙ ПОИСК Пингала дает специальные имена всем трехсложным измерениям: -- — — = хТ (ш), - — — = хТ (у) — — = Т (г), — =ТТ (з), — — =6 (Ф), — — - =31 О), — = хТ (ЬЬ), — =ц (и).
(3) И с тех пор все нзучающие санскрит должны заучивать их наизусть. Давным-давно кто-то разработал способ запоминания зтих кодов, придумав несуществующее слово раша(агахабйапаха(арам ( .). Смысл в том, что десять слогов зтого слова можно записать как уа шй са га )а ЬЬК па за 1а баш, после чего каждый трехсложный шаблон начинается с его имени. Происхождение слова раша$агехабйапааа(адатп неизвестно; Свбхаш Как (ЯпЬЬазЬ Кай) [1ш))ап Х Н)згогу оу Яс)енсе, Зб (2000), 123-1271 проследил его до книги С.Р. Вготгп Яане)гг1г Ргоях)у (1869), с. 28; таким образом, его можно считать наиболее ранним известным "циклом де Врейна*' для кодирования бинарных п-кортежей. арсис (вгяе) — тезис ($Ьеем) гиперпнррихий (арокелевеаматвк) (рхосе1ееешабе) четвертый пеон ИоиггЬ ршоп) третий пеев (хЬпб ряов) поник меньший (нисходящий) (пппог юшс) второй пеон (несение ряов) диямб (ЙшшЬее) аитнспает (авеврезг) первый зпитрит (Йхех ер1ег1ге) (б) первый пеон (бгее ржов) хориямб (сЬопашЬае) дитрохей, лихарев (ЙегоеЬее) второй зпитрит (еееовб ерйпхе) поник больший (восхоляший) (ша)ог юшс) третий зпитрит (тЫгт( ерагаЕ) четвертый эпятрит (ТоппЬ ерапге) диепондей (Йеропйее) пиррихнй (рушЬЫ) — ямб (шшЬие) трохей (хорей) (ггосЬее) — — епеядей (ерош)ее) трибрахий (гпЬгасЬ) елапеет (вверен) амфибрахий (ашрЫЬгаеЬ) бакхий (ЬвссЫее) дактиль (йвсгу1) амфимакр (ашрЫгааеег) автибакхий (рабшЪаееЫее) полосе (шЫоееее) сделано для ьувкжш$анаТа,ого Тем временем в Европе.
Классическая греческая паззия также основывалась на группах коротких и~или длинных слогов, называемых метрической стопой (шегг(са) хее1), аналогично тактам в музыке. Например, два коротких слога '- ' назывались ппррихий, а два длинных ' — — ' — снондей, поскольку зти ритмы использовались соответственно в песнях войны (хор(х)(0) и мира (охотбш). Греческие названия метрических стоп ассимилировались латынью и в конечном счете современными языками, в том числе английским: 74 КОМБИНАТОРНЫЙ ПОИСК Правило Секи для генерации перестановок достаточно привлекательно, но, к сожалению, оно не работает при и > 4. Похоже, эта ошибка оставалась незамеченной столетиями. [См. т*.
Мйапп, ТЬе Уете!ортеп! от" Ма!Ьеюпа!)сз ш СЬ(па апд 1арап (1913), 191-199; Та)п))аакп Бей'з Со))ес!ед )тот)сэ (Овайа, 1974), 18 — 20.] Чтобы взбежать многословия, рассмотрим этот вопрос вкратце, поскольку наука о вычислениях — это океан без границ. — Бхвсквра (ВЬазкага) (около 1150) Интересный список сочетаний имеется в знаменитой работе по алгебре А1-Ва)пг б'1-Ь7ваЬ (Блистательная кинга о вычислениях), написанной аль-Самавалем (а)-Ба!ватт'а1) из Багдада в 1144 году, когда ему было всего 19 лет. В заключительной части работы он представал список из ('О) = 210 линейных уравнений с 10 неизвестными: (!) к, +хо+к,+х,+к~+хо=65 (2) к,+к,+кз+кд+~;+к, 70 (5) х,+х2Ок,+х,+х,+ко 75 то(тт) 'т'а(тт'1 Ло(ттт да У. 'т'о '1. ллут( ЛЛУЪа (209) х,+хо+к,+хо+к,+хо=9! (2!0) ко+ко+х1+к~+ха+к1о )ОО Каждое сочетание шести из десяти элемен*гов дает одно из уравнений. Целью альСамаваля, несомненно, была демонстрация переопределенной системы линейных уравнений, которая, тем не менее, имеет единственное решение; для приведенной системы оно имеет вид (к!,хо,...,кта) = (1,4,9,16,25,10,15,20,25,5).
[Ба)аЬ АЬ- шао) апб ВовЬгй ВваЬед, А1-Вйпг еп А!®ФЬге оГАв-Явша7т'а1 (Пашввспв, 1972), 77-82, т(л-тт).[ сделано для итум!атанаса,ого Списки сочетаний. Наиболее ранний исчерпывающий список сачешаний, выдержавший разрушительное действие времени, находится в главе 63 последней книги Сусруты (Япагп(а), представляющей собой трактат о медицине и написанной до 600 года (вероятно, намного ранее). Заметив, что лекарства могут быть сладкими, кислыми, солеными, острыми, горькими и/или вяжущими, Сусрута старательно перечислил все (15,20,15,6,1,6) случаев, когда одновременно встречаются два, три, четыре, пять, шесть и одно кз этих качеств.
Бхаскара (ВЬавйага) повторил этот пример в разделах 110-114 своей книги ЙВата(! н заметил, что те же самые рассуждения применимы и к шестисложным стихотворным шаблонам с заданным количеством длинных слогов. Однако он просто упомянул конечные их количества (6, 15, 20, 15, 6, 1), без перечисления самих сочетаний. В разделах 274 и 275 он заметил, что числа (и) (и — 1)... (и — Ь + 1)/()о()о — 1)... ... (1)) указываке наряду с количеством сочетаний количество кампавиций (сошрошнопв), т.е. упорядоченных разбиений, однако это замечание также сделано без приведения полного списка. 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЪЕКТОБ 75 Игральные кости.
Определенный проблеск в области элементарной комбинаторики был и в средневековой Европе, особенно в связи с вопросом о всех возможных сочетаниях выпадения трех костей. Разумеется, существует всего (э) = 56 способов выбрать трн элемента нз шести при разрешенных повторениях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
