Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 20
Текст из файла (страница 20)
Интересный алгоритм для перечисления всех разбиений множества был впоследствип открыт Тошиаки Хондой (ТоэЫаЫ Нопба) (см. упражнение 24). Более де. тэльную информацию о генджи-ко и ее связи с историей математики можно найти в статьях ТашаЫ Уапо, Епкайп бепипаг, 34, 11 (Хоъ . 1995), 58 — 61; 34, 12 (Рес. 1995) „ 56-60. Разбиения множеств оставались практически не известными в Европе до гораздо более позднего времени, за исключением трех не связанных между собой случаев. Во-первых, в 1589 году Георг и/илн Ричард Паттенхам (Оеогб аплот В1сйап) РпФФепЬшп) опубликовал книгу ТЬе Аг1е оУЕпбйяЬ Роегэе, на с.
70-72 которой содержатся диаграммы, похожие на диаграммы генджи-ко. Например, приведенные ниже семь диаграмм использованы для иллюстрации возможных схем рифм в пятистрочных стихах, "где некоторые нз них грубее и неприятнее для уха, чем иные". Но этот визуально привлекательный список был неполон (см. упражнение 25). 1) 1 — 8 ~2э Во-вторых, неопубликованная рукопись Г.В. Лейбница (0.%. ?е1Ьшв) конца ХУП века свидетельствует, что он пытался вычислить количество способов разбиения множества (1,..., и) на три или четыре подмножества, но практически безуспешно.
Он посчитал ( з ) очень громоздким методом, который не позвгшил ему легко заметить, что (чз) = 2" ' — 1. Лейбниц попытался вычислить ( э) и (2) сделано для ькълкиИанайа.ого 88 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 только для и < 5 и сделал несколько числовых ошибок, что привело его к неверному ответу. [См.
Е. КпоЫосЬ, Бгийа Ье)бшг!апа Бпрр)ешепеа, 11 (1973), 229-233; 16 (1976), 316-32Ц Третий европейский случай разбиений множества носит совершенно иной характер. Джон Уоллис (доЬп %а11!э) посвятил третью главу своей книги В!эсопгэе ог" СошЬ1панопэ (1685) вопросу о "кратных частях", истинных делителях чисел, в частности он изучал множество всех способов разложения данного числа на множители. Этот вопрос эквивалентен задаче о разбиениях мрльшимнолсесглеа; например, разложения р~д~г по сути то же, что и разбиения мультимножества (р, р, р, д, д, г), где р, д и г -- простые числа. Уоллис разработал превосходный алгоритм для перечисления всех разложений данного целого числа и, по сути предвосхитив алгоритм 7.2.1.5М (см. упражнение 28).
Однако он не исследовал важные частные случаи, когда п представляет собой степень простого числа (эквиввлентно разбиениям целого числа) или когда п не содержит квадратов (эквивалентно разбиениям множества). Таким образом, хотя Уоллис и мог решить более общую задачу, ее сложность парадоксальным образом увела его с пути открытия разбиений чисел, чисел Белла, количества подмножеств Стирлинга и разработки простых алгоритмов генерации разбиений целых чисел или разбиений множеств.
Разбиения целых чисел. Разбиения целых чисел выходили на сцену комбинаторики еще медленнее. Епископ Вибольд (1т'!Ьо)о) (около 965 года) знал о разбиениях целых чисел на три части, не превышающие 6. О том же знал и Галилей (Оа!йео), который написал о ннх небольшую работу (около 1627 года) н который изучал частоты выпадения очков при бросании трех игральных костей. [Зорге !е эсорегге Ие 1 аай, в его работе (Орете, Уо1. 8, 591-594) Галилей перечислил разбиения в уменьшающемся лексикографическом порядке.] Мерсенн (Мегэеппе) перечислил разбиения 9 на любое количество частей на с. 130 своей книги Тгшгея г(е!а Ъо)х еФ деэ СЬапгя (1636). Для каждою разбиении 9 = а~ + + .
+ аь он, кроме того, вычислил мультиномиальный коэффициент 9)Да1!... аь!); как мы видели ранее, его интересовало количество различных мелодий, например он знал, что имеется 9!/(3)3(3!) = 1680 мелодий из девяти нот (а, а, а, Ь, Ь, Ь, с, с, с) . Однако он не упомянул случаи 8+ 1 и 3+ 2+ 1+ 1+ 1+ 1, вероятно потому, что не перечислял возможности каким-либо систематическим путем. Лейбниц (1е!Ьшз) рассматривал разбиения на две части в задаче 3 в работе Р!ээеггано г(е Аде СошМпатог!а (1666), а его неопубликованные заметки указывают, что впоследствии он потратил немало времени, пытаясь перечислить разбиения, состоящие из трех и более слагаемых.
Он называл их (разумеется, на латыни) "йэсегрг)опэ" или реже кйтп)э)опэ", а иногда — разделами ("эесг!опэ"), рассеянием ("йэрегэюпэ") или даже разбиениями ("раг1!1!опэ"). Они интересовали его в первую очередь изза их связи с мономиэльными симметричными функциями 2,'х х .... Однако множество попьпок Лейбница почти всегда приводили к неудаче, за исключением случая трех слагаемых, когда он почти (но не совсем) открыл формулу для [~з[ (см. упражнение 7.2.1.4-31).
Например, он аккуратно сосчитал только 21 разбиение 8, упустив случай 2+ 2+ 2+ 1+ 1, а для р(9) он получил только 26, потеряв 3+ 2+ +2+2, 3+2+2+1+1, 2+2+2+1+1+1 н 2+2+1+1+1+1+1, несмотря на то что он пытался перечислять разбиения систематически в убывающем лексико- сделано для эдэдъдлпГапага.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 89 графическом порядке, [См.
Е. КпоЫосЬ, бсисИа Ье!Ьша!апа бирр!ешеп1а, 11 (1973), 91 — 258; 16 (1976), 255-337; Н!згог!а Масйепшнса, 1 (1974), 409-430.) Де Муавр (де Мо|тге) был первым, реально достигшим успеха при изучении разбиений в своей статье "Метод возведения бесконечного многочлена в любую заданную степень, или извлечение из него заданного корня'" (РЫозорЬ!са! ггапеасгюпз, 19 (1697), 619-625 и рис.
5). Он доказал, что коэффициент прн г +" в (аз + Ьгг + сгз + +. )™ имеет по одному члену для каждого разбиения и; например, коэффициент при г + равен )а ~Ь +5(™з)а ~5~с+4(™4)а 4Ь а+6(™4)а~ 4Ьгсг+ +3( з )а -гЬге+6( г )а -гЬса+2( г )а гЬ(+ +(™з)а зсз+2(™г)а гсе+(г)а ~а'+(™1)а'" ~д. (29) Если мы положим а = 1, то член со степенями Ь'сто~с~... соответствует разбиению с 1 единицами, у двойками, й тройками и т.д.
Так, например, при и = 6 он получил разбиения в порядке 111111,11112,1113,1122,114,123,15,222,24,33,6, (30) Он пояснил, как перечислить разбиения рекурсивно (хотя и другим языком, связанным с его собственными обозначениями): для Й = 1, 2,..., и начинаем с Й и добавляем (ранее перечисленные) разбиения а — Ь, наименьшая часть которых не меньше Ь. (Мое решение! упорядочено перед публикацией, не столько для красоты, сколько в процессе некоторых размышлений, не достойных внимания любителей истины, Абрахам де Муввр (А(явйвт Не Мо(тте) (1717) П.Р.
де Монморт (Р.Н. бе Моптшогг) протабулировал все разбиения чисел ( 9 на количество частей < 6 в своем труде Еэзау д'Апа!уее зиг !ее .7ецх де Наяагс! (1708) в связи с задачей об игральных костях, Его разбиения перечислены в ином, чем в (30), порядке, например: 111111,21111,2211,222,3111,321,33,411,42,51,6. (31) По-видимому, Монморт не был знаком с работой де Муавра. До сих пор практически никто из рассмотренных нами авторов ие описал использовавшуюся им процедуру генерации комбинаторных шаблонов.
Мы можем только догадываться об их методах (или их отсутствии), изучая опубликованные ими списки. Волее того, в таких редких случаях, как статья де Муавра, в которой имесшсл явно описанный метод, автор полагает, что существуют списки всех шаблонов для случаев 1„2,..., и — 1, перед тем как приступить к созданию списка для случая и. За исключением Кедары (Кейага) и Нараямы (Ь!агауапа), ни один из авторов не привел метода генерации шаблонов "на лету", когда очередной шаблон получается из предшествующего непосредственно, без просмотра вспомогательных таблиц, сделано для итлудп(апаса.ого 90 КОМБИНАТОРНЫЙ ПОИСК Естественно, что современные программисты предпочитают более прямые методы, требующие меньшего количества памяти. Р.И.
Бошкович (И.Д. Воесот1сЬ) опубликовал первый прямой алгоритм для генерации разбиений в Сюгпа)е де' Ьеггегаг1 (Ноше, 1747), с. 393-404, вместе с двумя таблицами (с. 404). Его метод, который для п = 6 дает выход 111111,11112,1122,222,1113,123,33,114„24,15,6, (32) генерирует разбиения в точности в обратном порядке по отношению к порядку, получаемому прн работе алгоритма 7.2.1.4Р. Метод Бошковича, по сути, описан в разделе 7.2.1.4, с тем исключением, что обратный порядок приводит к несколько более простому н быстрому алгоритму, чем порядок, выбранный Бошковичем.
Бошкович опубликовал продолжение своей работы в Сюгпа1е пе' Ьеггегаг1 (Ногае, 1748, с. 12-27 и 84-99), развив свой алгоритм в двух направлениях. Во-первых, он рассмотрел генерацию только тех разбиений, части которых принадлежат заданному множеству Я, с тем чтобы возводить в т-ю степень символьные полнномы с разреженными коэффициентами. (Он утверждал, что наибольший общий делитель всех элементов 8 должен быть равен 1; в действительности, однако, его метод не работает, если 1 ф Я.) Во-вторых, он разработан алгоритм для генерации разбиений н на гп частей для заданных и н гп. И опять ему не повезло: для решения этой задачи впоследствии был разработан более удачный алгоритм 7.2.1.4Н, что лишило Бошковича шансов на славу, Ода Гинденбургу.
Изобретателем алгоритма 7.2.1.4Н был Карл Фридрих Гинденбург (Саг1 гг1ег)г1сЬ НшбепЬпгй), который "переоткрыл" алгоритм Нараяны 7.2.1.2Ь— способ генерации перестановок мультимножества. К сожалению„этот небольшой успех привел его к вере в то, что он осуществил революционный прорыв в математике (хотя он и снизошел до того, что упомянул других исследователей, в частности де Муавра, Эйлера и Ламберта, которые близко подошли к аналогичным открытиям). Гинденбург был в числе основателей первых математических журналов Герма. нин (издававшихся в 1786-1789 и 1794-1800 годах) и автором статей в них. Он неоднократноо занимал должность декана в университете Лейпцига (1)штегэ(гу ог Ье1ря18), а в 1792 году был его ректором.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
