AOP_Tom3 (1021738), страница 31
Текст из файла (страница 31)
НапРимеР, если задана пеРестановка (,1 э э е э ), действУем следУющим обРазом: (7) Вставка 7: Вставка 2; Вставка 9: (12) Вставка 5; Вставка 3: Значит, пара диаграмм (Р, 1~), соответствующая перестановке (г ~ ~э з з) (13) Из построения ясно, что Р и Я всегда имеют одну форму.
Кроме того, поскольку элементы всегда добавляются на границу Я и в порядке возрастания, то Я диаграмма. Обратно, если заданы две диаграммы одинаковой формы, то оютветствующий двухстрочный массив (11) можно построить так. Пусть элементами Я являются Пусть также р; есть элемент х, который удаляется из Р по алгоритму 0 с использованием значений э и 6, таких, что 96~ — — 96 причем 6 = п,..., 2, 1 (именно в таком порядке). Например, если применить это построение к диаграмме (13) и производить вычисления, обратные (12), до тех пор, пока Р не исчерпается, то получится массив (г з е ь з).
Поскольку алгоритмы 1 и П взаимно обратны, взаимно обратны и описанные здесь два построения; таким образом, требуемое взаимно однозначное соответствие установлено. 1 Соответствие, определенное в доказательстве теоремы А, обладает множеством поразительных свойств, н теперь мы приступим к выводу некоторых из них. Убедительная просьба к читателю: прежде чем двигаться дальше, выполните упр. 1, чтобы освоить методику построений. Как только элемент вытеснен из строки 1 в строку 2, он уже не влияет на строку 1; кроме того, строки 2, 3, ...
строятся из последовательности "вытесненных" элементов так же, как строки 1, 2, ... строятся из исходной перестановки. Это наводит на мысль о том, что на построение в теореме А можно взглянуть иначе, обращая внимание лишь на первые строки Р и Я. Например, перестановка (' э ) вызывает следующие действия нэд строкой 1 (ср. с (12)); 1: Вставить 7, присвоить |,166 <- 1. 3: Вставить 2, вытеснить 7.
5: Вставить 9, присвоить Ощ с — 5. 6: Вставить 5, вытеснить 9. 8: Вставить 3, вытеснить 5. (14) Таким образом, первая строка Р— это 2 3, а первая строка 4„1 — это 1 5. Кроме того, остальные строки Р и Я составляют диаграммы, соответствующие "вытеснен- ному" двухстрочному массиву (6 6 ° ) (15) Чтобы понять, как строится строка 1, проанализируем элементы, попадающие в некоторый заданный столбец этой строки.
Будем говорить, что пара (67ь р;) принадлежит классу 1 двухстрочного массива с 96 67з 67~ '1 676 < Чг < . ° < 67„, (1 ) р6 рх ри / РМ РЗ,, р„раЗЛИЧНЫ, (16 (17) если после применения алгоритма 1 последовательно к рмрз,..., рь начиная с пустой диаграммы Р, оказывается, что р; = Рм, (Напомним, что алгоритм 1 всегда вставляет данный элемент в 1-ю строку.) Легко видеть, что (дь р;) принадлежит классу 1 тогда и только тогда, когда р; имеет 6 — 1 инверсий, т. е, тогда и только тогда, когда р, = пнп(рмрг,,р,)— "левосторонний минимум'! Если в массиве (16) вычеркнуть столбцы класса 1„то получится двухстрочный массив (Чн Р»1) .
(9»2~Р»1)2 чтобы выполнялись неравенства 9», с 96 с с 9».* (18) Р11 ~ Р»2 ~ Р»1 ~ поскольку в процессе выполнения алгоритма вставки позиция диаграл»мы Рм принимает убывающую последовательность значений Р;„..., Р;„. В конце построения Рм =Р»„Ю!» = В»„ (19) а вытесненный двухстрочный массив, которым определяются строки 2, 3, ... диа- грамм Р и Я, содержит столбцы с Ч»2 9»2 " рл1 Р21 Р»2 ''' Р» ° — 1 (20) и другие столбцы, аналогичным образом полученные из других классов.
Эти рассуждения приводят нас к простому методу вычисления Р и Я вручную (см. упр. 3), а также предоставляют средства для доказательства одного весьма неажиданнога результата. Теорема В. Есл!» в построении нз теоремы А перестановка соответствует диаграмме (Р,ь„»), то обратная ей перестановка соответствует диа- грамме (»„», Р).
Эта довольно удивительный факт, потому что в теореме А диаграммы Р и Я формируются совершенно разными способами и обратная перестановка получается в результате весьма причудливой перетасовки столбцов двухстрочнога массива. Доказательство. Предположим, имеется двухстрочный массив (16); поменяв места- ми его строки и рассортировав столбцы так, чтобы элементы новой верхней строки расположились в порядке неубывания, получим "обратный" массив Рт ° ° ° Р11 Р! Рэ Р 9! (2! 92 ' ' ' Чп / Я! 92 ° ° ° Я РВЗЛИЧНЫ такай, что пара (д, Р) принадлежит классу 1 относительно (17) тогда и толька тогда, когда она принадлежит классу 1+ 1 относительно массива (16).
Операция перехода от (16) к (17) соответствует удалению крайней слева позиции строки 1. Это дает систематический способ опРеДелениЯ классов. НапРимеР, в пеРестановке (т т В 5 з) »1 3 5 В В левосторонними минимумами являются элементы 7 и 2, так что класс 1 — это ((1,7), (3,2)); в оставшемся массиве (В В В) все элементы минимальны, так что класс 2 — эта ((5,9), (6, 5), (8, 3)). В "вытесненном" массиве (15) класс 1 — эта ((3,7), (8,5)), а класс 2 — ((6,9)). Для любага фиксированного г элементы класса 1 можно так пометить Покажем, что эта операция соответствует взаимной замене Р и»г' в построении из теоремы А.
В упр. 2 наши замечания об определении классов переформулированы таким образом, что класс, к которому относится пара (дг,р;), не зависит от того факта, что элементы дг, ггэ,..., д„расположены в порядке возрастания. Поскольку результирующие условия симметричны относительно д и р, операция (21) не нарушает структуру классов; если (д,р) принадлежит классу Г относительно (16), то (р,4) принадлежит классу г относительно (21). Поэтому, если разместить элементы последнего ~~~с~~ Г так, ~тобы р» <'''<р»» <р», 9г» » йм > 63 то по аналогии с (16) получим (22) Рм = 4п, Ягг = рц, (23) как в (19), а столбцы р',, " рн рп ') 4»» чгз гп»»г (24) войдут в вытеснеяиый массив, как в (20). Следовательно, первые строки Р и Я меняются местами.
Кроме того, вытесненный двухстрочный массив для (21) является обратным по отношению к вытесненному двухстрочному массиву для (16), так что доказательство завершается применением индукции по числу строк в диаграмме. 3 Ясно, что элемент в левом верхнем углу диаграммы всегда наименьший. Это наводит на мысль о возможном способе сортировки множества чисел. Сначала можно составить из них диаграмму, многократно применяя алгоритм 1, н в результате наименьший элемент окажется в углу.
Затем этот наименьший элемент удаляется, а остальные элементы переразмещаются так, чтобы образовалась другая диаграмма; потом удаляется новый минимальный злемент и т. д. Поэтому давайте посмотрим, что происходит, когда мы удаляем угловой элемент из диаграммы (25) После удаления 1 на освободившееся место необходимо поставить 2. Затем можно поднять 4 на место 2, однако 10 нельзя поднять на место 4; на зто место можно Следствие. Количество диаграмм, которые можно сформггровать нз элементов (1, 2,..., и), равно количеству ггнволюггггй множества (1, 2...,, и). Довазашельспгео.
Если гг — инволюция, соответствующая паре диаграмм (Р,Я), то гг = гг соответствует паре Я,Р). Следовательно, Р = Ц. Обратно, если ив какая-либо перестановка, соответствующая паре (Р,Р), то к тоже соответствует паре (Р,Р); отсюда гг = в, Таким образом, существует взаимно однозначное соответствие между инволюциями х и диаграммой Р. 1 подвинуть 9, а потом 12 — на место 9, В общем случае приходим к следующей процедуре. Алгоритм Я (Удаление углового элеменша). Этот алгоритм удаляет элемент из левого верхнего угла диаграммы Р и перемещает остальные элементы так, чтобы сохранились свойства диаграммы.
Далее используются те же обозначения, что и в алгоритмах 1 и Р. Я1. [Начальная установка.] Присвоить г +- 1, г <- 1. Я2. [Выполнено?) Если Р„= оо, то процесс завершен. ЯЗ. [Сравнить.) Если Р~,+0, < Рц,+0, то перейти к шагу Я5. (Сравниваем элемен- ты справа и снизу от свободного места и передвигаем меньший из них.) Я4. [Сдвиг влево.) Присвоить Р„, +- Р,~,+ц, г <- г + 1 и вернуться к шагу ЯЗ. Яб.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
