Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 15
Текст из файла (страница 15)
Например, диаграмма Юнга формы (б, 4, 4, 1) нмеет внд Диаграммы такой формы ввел Альфред Юнг (А)ггед гоппй) в 1900 году в качестве вспомогательного средства прн изучении матричного представления перестановок. 1См. Ргос. йонг(оп Магй. Вос. (2) 28 (1928), 25о-292; Вгпсе К. Яайап, ТЬе Яуттегг1с Сгопр (Рас(бс Стоге, СаИ.: %гг(ятгогсЬ й Вгоойя/Со1е, 1991).) Для краткости вместо "диаграмма Юнга" мы будем говорить просто "диаграмма".
Ипеолюцил' — это перестановка, обратная самой себе. Например, существует 10 ннволюций множества (1, 2, 3, 4): 1234 2134 3214 4231 1324 1234 1234 1234 1234 1234 Термин "ннволюцня" первоначально использовался в классических задачах геометрия; инволюцни в общем смысле, рассматрнваемые здесь, были впервые изучены Х. А. Роте (Н. А. ВотЬв), когда он ввел понятие обратной перестановки (см.
раздел 5,1.1). Может показаться странным, что мы рассматриваем диаграммы н ннволюцнн вместе, но существует удивительная связь между этими понятиями, не имеющимн, казалось бы, друг к другу никакого отношения." число плволюцнй множества (1, 2,..., и) равно числу диаграмм, которые можно срормировать нз элементов (1, 2,..., и). Например, из (1, 2, 3, 4) можно сформировать ровно 10 диаграмм: 3 124 2 123 13 12 Это соответствует 10 ииволюциям (2). Такая связь между инволюциями и диаграммами отнюдь ие очевидна, и, по-видимому, не существует простого способа ее доказательства. Доказательство, которое мы обсудим, включает интересный алгоритм построения диаграмм, обладающий и другими неожиданными свойствами; он основан на особой процедуре вставки в диаграмму новых элементов.
Предположим, например, что нужно вставить элемент 8 в диаграмму (4) Метод, которым мы будем пользоваться, состоит в том, чтобы сначала поместить 8 в 1-ю строку, в клетку, ранее занимаемую 9, поскольку 9 — наименьший нэ элементов этой строки, больших 8, Элемент 9 "вытесняется" вниз, в строку 2, где он замещает 10. Затем 10 "вытесняет" 13 из З-й строки в 4-ю и, поскольку в 4-й строке нет большего элемента, чем 13, процесс завершается добавлением 13 в правый конец строки 4.
Наша диаграмма (4) преобразовалось в В алгоритме 1 содержится точное описание этого процесса и доказательство того, что он всегда сохраняет свойства диаграммы. Алгоритм 1 (Всшавка в диаграмму). Пусть Р = (Ру) — диаграмма целых положительных чисел, а к — целое положительное число, не содержащееся в Р. Этот алгоритм преобразует Р в другую диаграмму, содержащую х наряду с исходными элементами Р. Новая диаграмма имеет ту же Форму, что и старая, но на пересечении строки э и столбца 1 появился новый элемент, где э и 1 — величины, определяемые алгоритмом. (В этом алгоритме замечания в круглых скобках предназначены для доказательства его правильности, поскольку по индукции легко проверить, что эти замечания справедливы и что массив Р продолжает оставаться диаграммой на протяжении всего процесса.
Для удобства будем предполагать, что диаграмма ограничена нулями сверку и слева н снмволамн "со" — справа н снизу, так что элемент Рз определен при всех 1,,у > О. Если ввести отношение а < Ь тогда н только тогда, когда а<Ь нли а=Ь=О, или а=Ь=оо, то неравенства для диаграммы можно выразить в удобной форме: РО =О тогда и только тогда, когда 1= 0 или у = О," (у) Р~. <; Рц ч.м и Рз < Рцьм при всех 1,у > О.
Утверждение "х ф Р" означает, что либо х = оо, либо х ф Р; нн прн каких 1, у > 0.) 11. [Ввести х.] Присвоить 1 <- 1, х~ +- х и присвонть,| наименьшее значение, такое, что Р~ = оо. 12. (Найти хм.г.] (В этот момент РО м < х; < Ру и х; (с Р.) Если х; < Ру О, то уменьшить у на 1 и повторить этот шаг. В противном случае присвоить х;+~ +- РО и г; <- у.
13. ]Заменить элементом хь] (Теперь Рц П < х; < х;+г = Ру < Р1,+», РО 01 < х~ < х+э = РО < Р~;+цу и г; = 1.) Присвоить РО <- хь 14. ]х;+~ = оо?] (Теперь Рц 0 < Р„- = х; < х; .~ < Рц +О, Рп О- < Р; = х; < хм.! < Р~<+ц' га =д ила~.1 ф Р.) Если хы.1 ф со~ то увеличить( на 1 и вернуться к шагу 12. 15. ]Определить з, 14] Присвоить э +- г, г с- у' н закончить процедуру.
(К этому моменту условия (8) Рм Ф " ~(. ) = Рц ц = будут выполнены.) 1 Заметим, что данный алгоритм определяет "последовательность вытеснений" (9) х = хт < хз « х, < х,+~ = оо, а также вспомогательную последовательность индексов столбцов (10) при этом элемент Ргг меняет свое значение хге~ на х,, 1 < 1 < э. Например, когда в диаграмму (4) вставлялся элемент 8, последовательность вытеснения имела внд 8, 9, 10, 13, со, а вспомогательная последовательность — - 4, 3, 2, 2.
Мы могли бы переформулировать алгоритм так, чтобы он расходовал меньше временной памяти (необходимо хранить только текущие значения у, х; н хыа); последовательности (9) н (10) были введены с той лишь целью, чтобы можно было доказать некоторые интересные особенности этого алгоритма. Основное свойство алгоритма 1, которым мы не преминем воспользоваться, состоит в том, что алгоритм можно "прокрутить" в обратном направлении: по заданным э и «, определенным на шаге 15, можно привести Р к исходному виду, найдя и удалив элемент х, который был вставлен.
Рассмотрим, например, (5); пусть известно, что элемент 13 занимает позицию, которая раньше была пуста. Тогда элемент 13, наверное, был вытеснен вниз из 3-й строки числом 10, потому что 10 -- наибольший элемент в этой строке, меньший 13; аналогично элемент 10, по-видимому, был вытеснен из 2-й строки числом 9, которое, в свою очередь, было вытеснено нз 1-й строки числом 8. Таким образом, от (5) можно вернуться к (4). В следующем алгоритме подробно описан этот процесс.
Алгоритм 11 (Удаление иэ диаграммы). По заданной диаграмме Р и целым положительным числам э, «, удовлетворяющим условиям (8), этот алгоритм преобразует Р в другую диаграмму почти такой же формьп но с оо на пересечении столбца «и строки э. Найденный при этом элемент х удаляется из диаграммы Р. (Как и в алгоритме 1, пояснения в круглых скобках включены дэя облегчения доказательства того, что массив Р продолжает оставаться диаграммой на протяжении всего процесса.) Ш. [Ввести э, «.] Присвоить у +- «, 1 «- э, х,.~«+- «ю. Р2. [Найтих;.) (ВэтотмоментР; < х;„.«< Р««чп«их,„.~ фР.) Если РО «> < х; «, то увеличить у на 1 и повторить этот шаг. В противном случае присвоить х; « — Р;.
и г. «- у. 113. [Заменить элементом х;+«.) (Теперь Рцэ ц < Рп — — х, < х;+«Я Рц«+О, Рй 0 < Ру = х; < хьы < Р«;~.«у и г; = у,) Присвоить Р; «- х;~«. В4. [« = 1?) (теперь Рп 0 < х; < хьы = Р;, < Рц, О, Рп, у < х; < х;+, - Р," < Рб~«««и г; = у'.) Если «> 1, то уменьшить «на 1 н вернуться к шагу П2. ТИ. [Определить х.) Присвоить х « — х«и закончить процедуру, (Теперь 0 < х < со.) 1 Поясненпя к алгоритмам 1 и В, заключенные в круглые скобки, не только полезны для доказательства того факта, что зти алгоритмы сохраняют структуру диаграммы, но и позволяют убедиться, что алгоритмы 1 и П взаимно обратны. Если сначала выполнить алгоритм 1 с данной диаграммой Р н некоторым целым положительным числом х ««Р, то он вставит х в Р и определит целые положительные числа э, «, удовлетворяющие условиям (8).
Алгоритм П, примененный к полученному результату; восстановит значения х и первоначальный вид Р. Обратно, если сначала выполнить алгоритм П с данной диаграммой Р и некоторыми целым~ цоэожительными числами э, «, удовлетворяющими условиям (8), то он модпфицирует Р, удалив некоторое целое положительное число х. Алгоритм 1, примененный к полученному результату, восстановит значения э, «и первоначальный вид Р. Дело в том, что присвоения, приведенные в заключенных в скобки пояснениях к шаг,щ 13 и 04, равно как и к шагам 14 и 03, совпадают и однозначно определяют значение у. Слцэовательно, вспомогательные последовательности (9), (10) одинаковы в обоих случаях.
Теперь мы подготовлены к доказательству основного свойства диаграммы. Теорема А, Существует взаимно однозначное сгютэетстэне между множеством всех перестановок множества (1,2,...,и) и множеством всех упорядоченных пар длаграмм (Р,Ч), где Р н Я вЂ” диаграммы одинаковой формы из элементов (1, 2,..., и). (Пример к этой теореме содержится в примденном ниже доказательстве.) Дока«а«пельстео, Удобнее доказать несколько более общий результат. По пропзвольному двухстрочному массиву < 91 9« " йэ~ В<9«< "<д, (11) р| р«,-.
р„/ ' рмрз,".,р„различны, постРоим две соответствующие диаграммы Р и Ч', где Р состоит из элементов (ры. °,р ), а Я вЂ” из элементов (еы...,е„), причем Р я Ц имеют одинаковую форму. Пусть Р и 9 вначале пусты. При« = 1, 2, ..., и (именно в таком порядке) выполним следующую операцию: вставим р; в диаграмму Р при помощи алгоритма 1; затем установим Ям «- йь где «н г определяют вновь заполненную позицкю в Р. Напркмер, если задана перестановка (,', ««е «), действуем следующим образом: Ц7 Вставка 7: Вставка 2: Вставка 9: Значит, пара диаграмм (Р, Ч), соответствующая перестановке ( ~ ««««), имеет вид Р=59, 1«=36 (13) Из построения ясно, что Р и Я всегда имеют одну форму.
Кроме того, поскольку элементы всегда добавляются на границу Ч и в порядке возрастания„то Я— диаграмма, Обратно, если заданы две диаграммы одинаковой формы, то соответствующий двухстрочный массив (11) можно построить так. Пусть элементами 1«являются (6 6 6) (15) Чтобы понять, как строптся строка 1, проанализируем элементы, попадающие в некоторый заданный столбец этой строки. Будем говорить, что пара (вбчр;) принадлежит классу г двухстрочного массива < а а ". йь') В <йэ«" д., р1 рэ . ° р ! ' рьрэ,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
