Лекция 4 Перестановки. Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех. - презентация

Презентация на тему: " Лекция 4 Перестановки. Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех." — Транскрипт:

1 Лекция 4 Перестановки

2 Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех объектов а, b и с существует шесть перестановок: аbс, acb, bac, оса. cab, cba. Для множества из N элементов можно построить N! различных перестановок: первую позицию можно занять N способами, вторую (N – 1) способом, так как один элемент уже занят, и т. д. На последнее место можно поставить только один оставшийся элемент. Следовательно, общее количество вариантов расстановки равно N (N 1) (N 2). 1 = N! Далее будем рассматривать перестановки элементов множества

3 Инверсии Пусть даны базовое множество из N элементов 1,2, 3. N и его перестановка Пара называется инверсией (инверсионной парой) перестановки, если при i

4 Таблицей инверсий перестановки a 1,a 2. a N называется последовательность чисел b 1, b 2 …, b N, где b j есть число элементов перестановки, больших j и расположенных левее j (т. е. количество инверсий вида (x, j), при x > j). Например, для перестановки таблица инверсий: Свойство элементов таблицы инверсий: b N = 0, … 0 b i N – i, … 0 b 1 N – 1. Утверждение Таблица инверсий единственным образом определяет соответствующую ей перестановку.

5 Построение перестановки по таблице инверсий 1 способ: проход по таблице инверсий справа налево Создается заготовка перестановки из одного максимального числа. На каждом шаге в нее вставляется следующий по величине элемент с учетом того, сколько элементов, больших него, должно стоять перед ним. Пример: Таблица инверсий:

6 Алгоритм A1: построение перестановки по таблице инверсий справа налево Вход: N > 0 - количество элементов перестановки, b 1, b 2 …, b N – таблица инверсий, 0 b j N j. Р := пустая последовательность; цикл по j от N вниз до 1 вставить число j в Р после b j элементов; конец цикла; Выход: Р перестановка, соответствующая данной таблице инверсий

7 Построение перестановки по таблице инверсий 2 способ: проход по таблице инверсий слева направо Создается заготовка пустой перестановки длины N. На каждом шаге для каждого элемента перестановки, начиная с 1, отсчитывается в ней столько пустых ячеек, какое число записано в соответствующей позиции в таблице инверсий. В следующее за ними пустое место вставляется этот элемент. Пример: Таблица инверсий: Перестановка:

8 Алгоритм A2: построение перестановки по таблице инверсий слева направо Вход: N > 0 - количество элементов перестановки, b 1, b 2 …, b N – таблица инверсий, 0 b j N j. Р := последовательность из N пустых элементов ; цикл по i от 1 до N с шагом 1 выполнять пропустить b i пустых мест в P; поместить i на следующее пустое место; конец цикла Выход: Р перестановка, соответствующая данной таблице инверсий

9 Инверсионный метод поиска всех перестановок Таблица инверсий однозначно определяет перестановку и каждая перестановка имеет только одну таблицу инверсий. Следовательно, если мы сумеем перебрать все таблицы инверсий, то с помощью алгоритмов П1 или П2 сможем по ним восстановить все перестановки. Рассмотрим таблицу инверсий как N-значное число в такой необычной «системе счисления»: количество цифр, которое можно использовать в i-м разряде (с конца, начиная с 0) равно i. Возьмем «минимальную» таблицу и будем последовательно прибавлять к ней, как к числу, единицу, пользуясь, например, алгоритмом сложения с переносом для многоразрядных чисел, модифицированным для нашей «системы счисления».

10 Генерация таблиц инверсии … 1 11 … … … … 43 2 Шаг 0 Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5 Шаг 6 Шаг 7 Шаг 8 Шаг 9 Шаг 10 … Шаг 119

11 Алгоритм A 3 нахождение следующей таблицы инверсий Пусть B = b 1, b 2. b N – таблица инверсий, построенная на предыдущем шаге. Тогда следующая таблица инверсий получается из нее прибавлением к ней единицы: i := N; flag := истина; пока flag выполнять x := b i + 1; если x > N – i то начало b i := 0; i := i –1; конец иначе начало b i := x; flag := ложь; конец конец пока

12 Алгоритм Дейкстры : поиск следующей по алфавиту перестановки Пусть даны две перестановки b = b 1, b 2 …, b N и c = c 1, c 2 …, c N набора 1, 2. N. Говорят, что перестановка b предшествует перестановке с в алфавитном (лексико­графическом) порядке, если для минимального значения k, такого что b k c k, справедливо b k

13 Идея алгоритма Дейкстры : определить каким-либо образом функцию, которая по заданной перестановке выдает непосредственно следующую за ней в алфавитном порядке, и применять ее последовательно к собственным результатам начиная с самой первой перестановки, пока не будет получена последняя. Например, для перестановки следующей по алфавиту является перестановка

14 Алгоритм Дейкстры : генерация следующей по алфавиту перестановки Вход: N > 0 количество элементов; a 1, a 2, …, a N-1, a N – предыдущая перестановка. Шаг 1. Просматривая перестановку, начиная с последнего элемента, найдем такой номер i, что a i+1 >. > a N и a i a i. После этого поменять местами a i и a j. Шаг 3. Упорядочить «хвост» a i+1, …, a N по возрастанию. Для этого достаточно его инвертировать (обернуть в обратном порядке). Выход: следующая по алфавиту перестановка за данной.

15 Пример построения следующей по алфавиту перестановки Для перестановки Найти следующую по алфавиту ij Шаг 1: Шаг 2: Шаг 3: Поменять местами Обернуть хвост

16 Рекурсивный метод поиска всех перестановок Метод рекурсивного перебора перестановок основан на идее сведения исходной задачи к аналогичной задаче на меньшем наборе входных данных. Система рекуррентных соотношений, определяющих множество Реr(М) всех перестановок базового множества М произвольной природы: Реr(0) = , Реr(М) = Permut(i, M\), Permut(i, S) = . Первое равенство задает условие обрыва рекурсивного спуска: пустое множество элементов порождает пустую перестановку. Два последних равенства определяют правила рекурсивного перехода.