AOP_Tom3 (1021738), страница 21
Текст из файла (страница 21)
описать другие свойства перестановок и рассмотреть общий случай, когда допускается наличие одинаковых элементов. Попутно мьс многое узнаем о комбпнаторной математике, Свойства перестановок настолько красивы, что представляют и самостоятельный интерес. Удобно будет дать их систематическое изложение в одном месте, а не разбрасывать материал по асей главе.
Читателям, не имеющим склонности к математике, а также тем, кто жаждет поскорее добраться до самих методов сортировки, рекомендуется перейти сразу к разделу 5.2, потому что настоящий раздел непосредсшвенного отношения к сортировке почти не имеет. "5.1.1. Инверсии ПУсть а, а ...а„— пеРестановка множества (1,2,...,п). Если ! С 7' и а; > ам то пара (а„аз) называется инверсией перестановки; например, перестановка 3142 имеет три инверсии; (3,1), (3,2) и (4,2).
Каждая инверсия - - это пара элементов, "нарушающих порядок": следовательно, единственная перестановка, не содержащая инверсий, ... зто рассортированная перестановка 1 2... п. Такая связь с сортировкой и является главной причиной нашего интереса к инверсиям, хотя это понятие уже использовалосгч когда мы анализировали алгоритм динамического распределения памяти (см. упр. 2.2.2 — 9). Понятие инверсии ввел Г. Крамер в 1750 году в связи со своим замечательным правилом решения линейных уравнений (1п~г, а !'Апа!уэе йеэ 1ляпея СопгЬеэ А!64Ьг7диеэ (Оепеча, 1750), 657-659; см. также ТЬо|паэ Мшг, ТЬеогу оу Ое1егт1- папсэ 1 (1906), 11 — 14).
В сущности, он определил детерминант и х и-матрицы следующим образом: х~1 я|э ... я,„ як 1 хпэ ° ° три~ где сумма берется по всем перестановкам а1аз...а„из (1,2,...,п), а !пч(а1 аз... и„) — . число инверсий в перестановке. Таблица инверсий Ь~ Ьз... Ь„перестановки а, аз...а„образуется, ешли определить Ь как число элементов слева от 1, которые болыпе, чем !. Другими словами, Ь вЂ” число инверсий, второй элемент которых равен !. Отсюда, например, следует, что таблицей инверсий перестановки 59 1826473 будет (2) 2 3 6 4 О 2 2 1 О, поскольку 5 и 9 расположены левее 1; 5, 9, 8 — левее 2 и т.
д. Всего эта перестановка имеет 20 инверсий. По определению числа Ь всегда удовлетворяют неравенствам о<ь1<о — 1, О<Ьт<о — 2, ..., О<Ь„,<1, Ь„=О. (3) Пожалуй, наиболее важный факт, касающийся перестановок и установленный Маршаллом Холлом (Магвьай На!!), состоит и том, что таблица инверсий единственным образом определяет соответствующую перестановку.
[См. Ргос. Яушр. Арр!!ед Ма~6. 6 (Ашебсап Марш Бос!ейу, 1956), 203.) Из любой таблицы инверсии Ь1 Ьт... Ь„, удовлетворяющей условиям (3), можно однозначно восстановить перестановку, которая ее породила, путем последовательного определения относительного расположения элементов п,п — 1,...,1 (в этом порядке). Например, перестановку, соответствующую (2), можно построить следующим образом: выпишем число 9, затем разместим В после 9, поскольку Ьв = 1. Аналогично установим 7 после и В, и 9, поскольку Ьт = 2.
Так как Ьв = 2, то 6 должно следовать за двумя уже выписанными нами числами; таким образом, имеем промежуточный результат 9 8 6 7. Продолжим, приписав 5 левее, поскольку Ьв = 0; поместим 4 вслед за четырьмя из уже записанных чисел, а 3 — после шести выписанных чисел (т. е, в правый конец) и получим 5986473.
Вставив аналогичным образом 2 и 1, придем к (1), Такое соответствие важно, потому что часто можно заменить задачу, сформулированную в терминах перестановок, эквивалентной ей задачей, сформулированной в терминах таблиц инверсий, которая, возможно, решается проще. Рассмотрим, например, самый простой вопрос: сколько существует перестановок множества (1,2,..., и)? Ответ должен быть равен чиглу всевозможных таблиц инверсий, а их легко пересчитать, так как 61 можно выбрать и способами, Ьз независимо от Ь, — и — 1 способами, ..., а ܄— единственным способом; итого получаем п(п — 1)... 1 = и! различных таблиц инверсий.
Таблицы инверсий пересчитать легче, потому что значения Ьь полностью не зависят друг от друга, в то время как аь должны быть все различны. В разделе 1.2.10 мы рассматривали задачу о числе локальных максимумов перестановки, если читать ее справа налево. Иными словами, требовалось подсчитать количество элементов, каждый из которых больше любого из следук>щих после него. (Например, правосторонние максимумы в (1) — это 3, 7, 8 и 9.) Оно равно количеству индексов у, таких, что 6, имеет максимальное значение и — ~. Так как Ь, будет равно и — 1 с вероятностью 1/и н (независимо) Ьт будет равно и — 2 с вероятностью 1/(и — 1) и т.
д., из рассмотрения инверсий ясно, что среднее число правосторонних максимумов равно 1234 1423 3214 4123 3241 4321 Рис. 1. Усеченный октазлр,нв котором показано изменение числа инверсий, когда меня- ются местами два соседних элемента перестановки. 1 1 1 — + + + — =К,. п и — 1 1 Аналогичным способом легко получить и соответствующую про|гзводящую функцию. Ясно, что если поменять местами соседние элементы перестановки, то общее число инверсий увеличится или уменьшится на единицу. На рис. 1 показаны 24 перестановки множества (1, 2,3,4); линиями соединены перестановки, отличающиеся одна от другой положением днух соседних элементов; двигаясь вдоль линии вниз, мы увеличиваем число инверсий на единицу. Следовательно, число инверсий в перестановке я равно длине нисходящего пути из 1234 в х на рис.
1; все такие пути должны иметь одинаковую длину. Заметим, что эту диаграмму можно рассматривать как трехмерное твердое тело — "усеченный октаэдр", имеющий 3 шестиугольных и 6 квадратных граней. Это один из классических правильных многогранников, которые исследовал еще Архимед (см. упр, 10). Не следует путать "инверсии" перестановок 1пшегэ1опэ оГ а регшп1асюп) с обрашимжа перестановками (4посгзе оГ а регшц1а11оп). Вспомним, что перестановку можно записывать в виде двух строк: 1 2 3 .. п) аг аг аэ .. а„ / С4) Обратной называется перестановка а', а', аэ...а'„, которая получается, если в (4) поменять местами строки, а затем упорядочить столбцы в порядке возрастания по верхним элементам: (1 1 3 .
) ( (5) Например, обратной к перестановке 591826473 будет перестановка 359716842, так как 591826473') (123456789~ г 123456?89! 1,359716842/ Можно дать другое определение обратной перестановки: а' = й тогда и только ! тогда, когда аь =,1. Понятие обратной псрестаиовки впервые ввел Х. А. Роте (Н. А. ВосЪе) (в Яапип!нп8 сошЬ!пасет!ьт!папа!уг!эсЬ ег А!>БапсИипдеп, ес!1сес! Ъу К.
Г. Н!пдепЪигб, 2 (Ее1рз18, 1800), 263 — 305]. Он заметил интересную связь между обратными перестановками н инверсиями: обратная перестановка содержит ровно столько инверсий, сколько исходяая. Роте дал не самое простое доказательство этого факта, но оно поучительно и притом довольно красиво. Построим таблицу размером и х и, наподобие шахматной доски, в которой точки стоят в знй клетке мй строки, если а; = !1 После этого расставим крестики во всех клетках, снизу от которых (в том же столбце) и справа (в той же строке) есть точки.
Например, для 591 8 264 73 диаграмма будет выглядеть следующим образом; Количество крестиков раино числу инверсий, так как нетрудно видеть,что Ь равно числу крестиков в 7-и столбце. Если мы теперь транспонируем диаграмму (поменяв ролями строки и столбцы), то получим диаграмму для обратной по отношению к исходной перестановки; значит, число крестиков (число инверсий) одинаково в обоих случаях. Роте использовал данный факт для доказательства того, что детерминант матрицы ие меняется прп транспонировании. Для анализа некоторых алгоритмов сортировки необходимо знать число перестановок и элементов, содержащих ронпо Ь инверсий.
Обозначим это число через 7„(Ь): н табл. 1 приведено несколько периых значений данной функции. Из таблицы инверсий !б Ьз...Ь„ясно, что 1„(0) = 1, 1„(1) = и — 1 и что выполняется свойство симметрии: "((2) ) Далее, так как значения Ьь можно выбирать независимо одно от другого, нетрудно видеть, что производящая функция С„(э ) = 7„(0) + 7„(1) г + 7„(2) з~ + . (7) Таблица 1 ПЕРЕСТАНОВКА С Ь ИНВЕРСИЯМИ удовлетворяет соотношению 0„(а) = (1+ э+ + э" ')С„с(э); следовательно, она имеет довольно простой внд, как показано О. Родригесом (О. Вобс13цеэ) [Х сЕе Масйь 4 (1839), 236-240): (1 + с + . + г" ')...(1 + х)(1) = (1 — х")...(1 — с~)(1 — з)Д1 — г)".
(3) С помощью этой производящей функции можно легко продолжить табл. 1 и убедиться, что числа, расположенные под ступенчатой линией в таблице, удовлетворяют соотношению Е„(1с) = Е„()с — 1) + Е„с((с), где lс < п. (9) (Для чисел, находящихся над ступенчатой линией, это соотношение не выполня- ется.) Более сложные рассуждения (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
