Дискретная математика (998286), страница 25
Текст из файла (страница 25)
В этом случае подстановку у: 1..п -ь 1..п удобно задавать таблицей из двух строк. В первой строке — значения аргументов, ао второй — соответствующие значения функции. Пример 1 2 3 4 5~ ~1 2 3 4 5~ 5 2 1 4 3~ д )4 1 2 3 5~ Произведением подстановок у и д называется их суперпозиция У о д. Пример 5 1 4 3 2 толсдвстввнная подстановка зто подстановка е, такая что е(х) = х Пример 1 2 3 4 5 Обратная подстановка — зто обратная функция, которая всегда существует, по- скольку подстановка является биекцией. 14О Глава 5.
Комбинаторика ЗАМЕЧАНИЕ Таблицу обратной подстановки можно получить, если просто поменять местами строки таблицы исходной подстановки. Пример 1 2 3 4 5 т 3 4 2 1 5 1 2 3 4 5 Таким образом, множество подстановок образует группу относительно операции суперпозиции. Эта группа называется симметрической степени п. 5.2.2. Графическое представление подстановок Подстановки удобно представлять в графической форме, проводя стрелки от каждого элемента х к элементу йх).
Пример Графическое представление подстановки 1 2 3 4 5) 2 3 1 4 5~ представлено на рис. 5.1. Ю Ф Рио. б.т. Графическое првдставлвнив подстановки 5.2.3. Циклы Цикл — это последовательность элементов хо,..., хы такая что ~хт+т, О 41( Й, ~хо, т' = и. Цикл длины 2 называется тлранстээицией. 141 8.2.
Подстановки ЗАМЕЧАНИЕ Иэ графического представления подстановки наглядно видно цроисхожление термина «цикл». 5.2.4. Подстановки и перестановки В таблице подстановки нижняя строка (значения функции) является перестановкой элементов верхней строки (значения аргумента). Если принять соглашение, что элементы верхней строки (аргументы) всегда располагаются в определенном порядке (например, по возрастанию), то верхнюю строку можцо не указывать— подстановка определяется одной нижней строкой. Таким образом, подстановки взаимно однозначно соответствуют перестановкам. Перестановку (н соответствующую ей подстановку) элементов 1,...,п будем обозначать (а„..., а„), где все а; — различные числа из диапазона 1..п.
5.2.5. Инверсии Если в перестановке 1 = (а„..., а„) для элементов а, и а, имеет место неравенство а, > ау при 1 <,г', то пара (а,, а.) называется инверсией. Обозначим 1(1)— число инверсий в перестановке 1'. ТЕОРЕМА Произвольную подстановку 1 можно представить в виде супврпоэиции 1Ц) траиспоэиций соседних элементов. Дока 3лтел ьство Пусть У = (аы..., 1,..., а„). Переставим 1 на первое место, меняя ее местами с соседними слева элементами. Обозначим последовательность этих транспозиций через 1ы При этом все инверсии (и только они), в которых участвовала 1, пропадут.
Затем переставим 2 на второе место и т. д. Таким образом, 1 о 1г о с С„= е и по свойству группы 1=с„'о ос,', причем )сг)+Щ+ + ~1 ~ =1()) П СЛЕДСТВИЕ Всякая сортировка молсвт быть выполнена перестановкой соседних элементов. ОТСТУПЛЕНИЕ Доказанная теорема утверждает, что произвольную перестановку можно предатавить в виде композиции определенного числа транспознцнй, но не утверждает, что такое представление является эффективным. Метод сортировки, основанный на предшествующей теореме, известен как «метод пузырька». Заметим, что при перемещении элемента на свое место трансцозицнямн соседних элементов все элементы остаются на своих местах, кроме перемещаемого элемента и того элемента, который стоит на целевом месте, а этн элементы меняются местами.
Таким образом, метод пузырька может быть выражен в форме алгоритма 5д. Этот алгоритм прост, но является далеко не самым эффективным алгоритмом сортировки; 142 Глава 5. Комбинаторика Алгоритм 6.1. Сортировка методом пузырька Вход: массив А: аггау [1..и] оЕ 11, где значения элементов массива расположены в произвольном порялке и для значений типа В задано отношение <. Выход: массив А: аггау [1..и] оЕ 11, в котором значения расположены в порядке возра. стания. Еог т Еготв 1 Со и — 1 Йо ти: = т ( индекс кандидата в минимальные элементы ) Еог т' болт т + 1 Со и т)о 1Е А[Я < А[от] Г)тЕВ т: =у ( новый кандидат в минимальные ) евд!Е еЫ Еог А[!] т-т А[т] ( ставим минимальный элемент на место ) епт) Еог 5.2.6.
Генерация перестановок На множестве перестановок естественным образом можно определить упоряг]рг ченность на основе упорядоченности элементов. А именно, говорят, что перестановка (аы..., а„) лексикографически предтпествует перестановке (Ьт,...,Ь„), если Лй < и аь < Ьь ЕстЕЕ < й а; = Ь; (см. также упражнение 1.9.3). Аналогично, говорят, что перестановка (ат,...,а„) антилексикографически предшествует перестановке (Ьт,..., Ь„), если 3 й < и аь > Ьь ЕгЧ! > й а, = Ьо Следующий алгоритм генерирует все перестановки элементов 1,..., и в антилексикографическом порядке.
Массив Р: агтау [1ьи] оЕ1..и является глобальным и предназначен для хранения перестановок. Алгоритм 5.2. Генерация перестановок в аитилексикографическом порядке Вход: и — количество элементов Выход". последовательность перестановок элементов 1,...,и в антилексикографическом порядке. Еог т 6"овт 1 Го и Йо Р[!]:=! ( инициализация ) евт) Еог Авгйех(и) ( вызов рекурсивной процедуры Ап!!!ех ) Основная работа по генерации перестановок выполняется рекурсивной процеду- рой Ап01ех, Вход: ит — параметр процедуры — количество первых элементов массива Р, для которых генерируются перестановки.
Выход: последовательность перестановок 1,...,т в антилексикографическом порядке. !Е из = 1 ГЬЕВ у!е!д Р ( очерелная перестановка ) е1зе Еог т 6ош 1 Го т т)о Автг!ех(ят — 1) ( рекурсивный вызов ) тЕ ! < нт Ейев 1аЗ 5.2. Подстановки Р(1( е+ Р(гн( ( следующий элемент ) нечегзе(т — 1) ( изменение порядка элементов ) еш1 1Е еш1 Еог епо' ЕЕ Вспомогательная процедура Вечегве переставляет элементы заданного отрезка пассива Р в обратном порядке. Вход: Ь вЂ” номер элемента, задающий отрезок массива Р, подлежащий перестановке в обратном порядке.
Выход: первые й элементов массива Р перестзвлены в обратном порядке У: = 1 ( нижняя граница обрэ|нэемого диапазона ) чгййе у < й йо Рф <-~ Р(к( У:=)+1 Ь:=й — 1 еш) иййе Овос новднив Заметим следующее. Искомую последовательность перестановок и элементов можно получить из последовательности перестановок и — 1 элемента следующим образом.
Нужно выписать и блоков по (и — 1)! перестановок в каждом, соответствующих последовательности перестановок и — 1 элемента в антгглексикографическом порядке. Затем ко всем перестановкам в первом блоке нужно приписать справа и, во втором — и — 1 и т. д. в убывающем порядке. Затем в каждом из блоков (кроме первого), к перестановкам которого справа приписан элемент з, нужно в перестановках блока заменить все вхождения элемента 1 на элемент и. В полученной последовательности все перестановки различны, и их и(и — 1)! = и!, то есть перечислены все перестановки. При этом антилексикографический порядок соблюден: для последовательностей внутри одного блока, потому что этот порядок был соблюден в исходной последовательности, а для последовательностей на границах двух блоков, потому что происходит уменьшение самого правого элемента.
Обратимся к процедуре Аптйех — легко видеть, что в ней реализовано указанное построение. В основном цикле сначала'строится очередной блок — последовательность перестановок первых ги — 1 элементов массива Р (при этом элементы Р[нз[,..., Р[и] остаются неизменными). Затем элемент Р[ги) меняется местами с очередным элементом РЯ. Вызов вспомогательной процедуры Вечегзе необходим, поскольку последняя перестановка в блоке является обращением первой, а для генерации следующего блока на очередном шаге цикла нужно восстановить исходный порядок. С) Пример Последовательность перестановок в антилексикографическом порядке для и = 3: (1, 2, 3), (2„ 1, 3), (1, 3, 2), (3, 1, 2), (2, 3, 1),'(3, 2, 1), 144 Глава 5. Комбинаторика 5.3.
Биномиальные коэффициенты Число сочетаний С(тп, и) — это число различных и-элементных подмножеств тэлементного множества (см. подраздел 5.1.5). Числа С(т, и) встречаются в формулах решения многих комбинаторных задач. Действительно, рассмотрим следующую типовую схему рассуждений при решении комбинаторной задачи. Пусть нужно определить число подмножеств т-элементного множества, удовлетворяющих некоторому условию. Разобьем задачу на подзадачи: рассмотрим отдельно 1-элементные подмножества, 2-элементые и т. д., а затем сложим полученные результаты. К счастью, числа С(т,и) обладают целым рядом свойств, рассматриваемых в этом разделе, которые оказываются очень полезными при выкладках. 5.3.1.
Элементарные тождества Основная формула для числа сочетаний т.' С( Л)=тй, позволяет получить следующие простые тождества. ТЕОРЕМА 1. С(т,и) =С(т,т — и), 2. С(т,п) =С(тп — 1,п) +С(т — 1,п — 1), 3. С(и, т) С(т, т) = С(п, т)С(п — т, т — тп) . ДОКАЗАТЕЛЬСТВО т! т! С(т, т — п)— (т — п)1 (тп — (т - п))1 (т — п)1! п1 = С(т,п). С(т — 1,п)+С(т — 1,и — 1) = (т - 1)! (тп - 1)! + —. и! (т и 1)! (п 1)! !тп 1 (п (т' — 1)! (т — 1)! и(п — 1)! (т — и — 1)! (и — 1)! (т — п)(т и — 1)! (тп — и)(тп — 1)! + и(т — 1)! п(и — 1)! (т — и) (тп — п — 1)! (т — и+ п)(т — 1)! т! — — С(тп, и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
