Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 10
Текст из файла (страница 10)
упр. 2), тем не менее о тту = Ф та, если а и б не содержат общих букв, Аналогичным способом понятие цикла можно распространить на случай, когда злементы могут повторяться. Вудем записывать в виде (х1 ха ... х) (10) перестановку, двухстрочное представление которой получается путем устойчивой сортировки столбцов С*;, .:.;) (11) по верхним злементам. Например, 1'а Ь а и а с а а 6 т1"1 1' а а а 6 6 с Н ~1 а' Н "1 т 6 а т1 а с а а Ь с( т1/ ( с а 6 тт д а 6 а а д,/' а а Ь 6 6 6 Ь с с с И а Й Н И1 И Ь с Ь с а с т( а 0 Н Ь 6 Ь а'/ ' (12) Если можно записать к в виде о т Д, где а содержит, по крайней мере, одну букву а, то крайнее слева а в верхней строке двухстрочного представления а должно так что перестановка (4) фактически является циклом.
Мы могли бы описать зтот цикл словесно, сказав что-нибудь наподобие "4 переходит в 6, переходит в Н. переходит в а, переходит в ... переходит в тт н возвращается обратно". Заметим. что эти обобщенные циклы не обладают всеми свойствами обычных циклов: (х1 хз... х„)— необязательно то же самое, что и (хз ..,х„з1). В разделе 1.3.3 мы выяснили, что каждую перестановку множества можно единственным с точностью до порядка сомножителей образом представить в виде произведения непересекающихся циклов, где "произведение" перестановок определяется законом композиции. Легко видеть, что произведение непересекающихся циклов - — то же самое, что цх соединительное произведение; зто наводит на мысль о том, что можно будет обобщить полученные ранее результаты, если найти единственное (в каком-то смысле) представление и для произвольной перестановки мультимножества в виде соединительного произведения циклов, В действительности существует, по крайней мере, два естественных способа сделать зто, и каждый нз них имеет важные приложения.
Равенство (5) дает один способ представления с а Ь т( И а Ь д а И в виде соединительного произведения более коротких перестановок. Рассмотрим общую задачу о нахождении всех разложений х = а тб данной перестановки х. Для зтого полезно проанализировать конкретную перестановку, например оказаться над 4 значит, перестановка о должна содержать хотя бы одну букву И.. Если взглянуть теперь на крайнее слева гт в верхней строке о, то можно точно так же увидеть, что оно должно оказаться нвд а; значит, в а должны содержаться, по меньшей мере, дае буквы г1.
Посмотрев на второе г1, видим, что а содержит также 6. Единственное предположение о том, что о есть левый сомножнтель я, содержащий букву а, приводит к такому промежуточному результату: Продолжая рассуждать точно так же, обнаружим, что буква 6 в верхней строке (13) должна оказаться над с, и т. д. В конце концов, этот процесс вновь приведет нас к букве а, и мы сможем, если захотим, отождествить ее с первой буквой а. Такое рассуждение, по существу, доказывает, что любой левый сомножитель а в разложении перестановки (12), содержащий а, имеет вид (Н г( Ь с г( Ь Ь с а) т а', где а' — некоторая перестановка. (Удобно записывать а не в начале, а в конце цикла; это допустимо, поскольку буква а только одна.) Аналогично, если бы мы предположили, что и содержит букву Ь, то вывели бы, что о = (с г( г( 6) т о", где а" — некоторая перестановка. В общем случае зти рассуждения показывают, что еглгг есть какое-нибудь разложение а т,9 = тг, где и содержит данную букву у, то существует единственный цикл вида (хт ...
х у), п>0, хг,...,хФУ, который является левым сомножителем в разложения перестановки а. Такой цикл легко отыскать, зная я и у; это самый короткий левый сомножитель в разложении перестановки я, содержащий букву у, Из сказанною следует теорема. Теорема А. Пусть элементы мультнмножесгва М линейно упорядочены отношением "<". Каждая перестановка я мульгплгножества М имеет единственное представление в виде соединительного произведения я = (хгг ...хт,уг) т(хы...хз„хуз) т т(хм ...хш Уг), т ~ 0: (13) удовлетворяющее следующим двум условиям: уг<уз« уг и ут<хг при1<т<п;,1<туг. (16) (Иными словами, в каждом цикле последний элемент меньше любого другого и последние элементы циклов образуют неубывающую последовательность.) Даказательстаао.
При я = с получим требуемое разложение, положив г = О, В противном случае пусть уг — минимальный элемент в л-, .определим (хг г... хин уг)— самый короткий левый сомножитель разложения я, содержащий уг, как в рассмотренном примере. Теперь я = (хгг ... хьм Ут) т Р, где р — некоторая перестановка; применив индукцию по длине перестановки, можем написать Р = (хгп ° ° хзш уз) т ' т (хм ° хга, уг). где условия (10) выполнены. Тем самым доказано существование такого разложения, Докажем единственность разложения (15), удовлетворяющего условиям (16). Ясиз, что т = О тогда и только тогда, когда тт — куль-перестановка с. При т > О из (16) следует, что ут —.
минимальный элемент перестановки и что (х11 ... хт„, ут)— самый короткий яевый сомножитель, содержащий ум Поэтому (хм ... хгю ут) определяется однозначно; доказательство единственности такого представления завершается применением индукции и законов сокращения (7). $ Напрттмер, "каноническое" рвзложеиие перестановки [12), удовлетворяющее данным условиям, таково: (17) И И Ь с 4 Ь Ь с а) т (6 а) т (г 4 6) т (й), всяка<6<с<а, Важно отметить, что на самом деле в этом определении можно отбросить скобки и знаки операции т и зто не приведет к неоднозначности! В конце каждого цикла появляется наименьший из оставшихся элементов. Таким образом, наше построение связывает с исходной перестановкой х = а 6 с 6 с а с й а а а 6 6 6 а' перестановку х'= НттЬсаЬЬсаЬасаЬа.
Если в двухстрочном представлении тт содержится столбец вида "„где х < у, то в связанной с э' перестановке присутствует соответствующая пара соседних элементов ...ух.... Так, в нашем примере тт содержит три столбца вида эю трижды встречается пара а 6. Вообще, из этого построения вытекает замечательная теорема. Теорема В. Пусть М вЂ” - мульгвмножество. Существует взаимно одяозначное соответствие между перестаиовквми М, такое, что если я соответствует я', то выполняются слеэующяе условия: а) крвйянй слева зчемент к' равен крайнему слева элементу я; Ь) для всех лар участвующих в перестановке элементов (х, у), таких, что х < у, число вхождеиий столбца," в двухстрочное представление перестановки тг равно числу глучаев, когда в перествиовке я' элемент х следует пеаосредствеиио зв у.
$ Етли М -- множество, то зто, по суптеству, "нестандартное соответствие", которое обсуждалось и конце раздела 1.3.3, с незначительными изменениями. Волее общий результат теоремы В полезен при подсчете числа перестановок специальных типов„поскольку часто проще решить задачу с ограничениями, наложениыми на двухстрочное представление, чем эквивалентную задачу с ограничениями ва пары соседних элементов. П.
А. Мак-Магон (Р. А. МасМаЬоп) рассмотрел задачи этого типа в своей выдающейся кииге Сошбтпатогу Апа!уэтэ 1 (СашЬтуййе Питт. Ргеээ, 1915), 168-186. Он дал конструктивное доказательство теоремы В в частном случае, когда М содержит элементы лишь двух различных типов, скажем а и 6; его построеиие для этого случая, по существу, совпадает с приведенным здесь, ио представлено в совершенно ином виде. Для случая трех различных элементов а, 6, с Мак-Магон дал сложное неконструктивное доказательство теоремы В; общий случай впервые доказал Фоата (Ровса) [см.
Сотргев Иепдпэ Асяс(. Вот'. Рапэ 258 (1964), 1672-1675). В качестве нетривиального примера применения теоремы В найдем число строк букв а, 6, с, содержащих ровно А вхождений буквы а; В вхождений буквы б; С вхождений буквы г; Й вхождений пары стоящих рядом букв са: 1 вхождений пары стоящих рядом букв сб; ш вхождений пары стоящих рядом букв ба.
Из теоремы следует, что это то же вида А самое, что найти число двухстрочных массивов (' :) га а'в  — 1 Ь'э Сс'я Вуквы а можно расположить во второй строке способами; после этого буквы 6 можно разместить в оставшихся позициях способами. Остальные свободные места нужно заполнить буквами с; следовательно, искомое (20) Вернемся к вопросу о нахождении всех разложений данной перестановки. Существует ли такой объект, как "простая" перестановка, которая не разлагается на множители, отличные от нее самой и гУ Обсуждение, предшествующее теореме А, немедленно приводит к выводу о том, что перестановка будет простой тогда и только тогда, когда она является циклом без повторяющихся элементов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
