Перестановки элементов

Комбинаторика Скачать презентацию
<< Остовное дерево		Комбинаторика 9 класс >>

Фотографий нет

Фото из презентации «Перестановки элементов» к уроку алгебры на тему «Комбинаторика»

Автор: Joseph V Romanovsky. Чтобы познакомиться с фотографией в полном размере, нажмите на её эскиз. Чтобы можно было использовать все фотографии на уроке алгебры, скачайте бесплатно презентацию «Перестановки элементов» со всеми фотографиями в zip-архиве размером 143 КБ.

Скачать презентацию

Перестановки элементов

содержание презентации «Перестановки элементов»

Сл	Текст	Эф	Сл	Текст	Эф
1	Дискретный анализ. Комбинаторика. Перестановки.	0	13	перестановок - 2. Выпишем несколько следующих	0
2	Перестановки. Пусть задано множество из n	0		перестановок. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6,
	элементов. Упорядочение этих элементов называется			3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2,
	перестановкой. Иногда добавляют «из n элементов».			3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6, 7,
	Обычно выделяется одно, основное или естественное,			5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2,
	упорядочение, которое называется тривиальной			3, 5, 1, 6, 7).
	перестановкой. Сами элементы множества A нас не		14	Формальное описание алгоритма. Рабочее состояние:	0
	интересуют. Часто в качестве элементов берут целые			Перестановка p и булев признак isActive. Начальное
	числа от 1 до n или от 0 до n-1. Обозначим множество			состояние: В записана тривиальная перестановка и
	перестановок из n элементов через Pn , а его мощность			isActive = True. Стандартный шаг: Если isActive, выдать
	через Pn. Зададим все те же три вопроса: чему равно Pn,			перестановку в качестве результата. Двигаясь с конца,
	как перебрать элементы Pn , как их перенумеровать.			найти в перестановке наибольший монотонно убывающий
3	Теорема о числе перестановок. Число перестановок из	0		суффикс. Пусть k – позиция перед суффиксом. Положить
	n элементов равно n! - произведению чисел от 1 до n.			isActive := (k > 0). Если isActive, то найти в
	(n! читается n–факториал) Доказательство. По индукции.			суффиксе наименьший элемент, превосходящий pk, поменять
	Для n=1 формула очевидно верна. Пусть она верна для			его местами с pk, а потом суффикс «перевернуть».
	n-1, докажем, что она верна и для n. Первый элемент		15	Еще алгоритм перебора перестановок. Попробуем	0
	упорядочения можно выбрать n способами, а к выбранному			теперь перебрать перестановки так, чтобы две
	первому элементу можно способами приписать остальное.			последовательные перестановки мало отличались друг от
	Поэтому верна формула Pn= Pn-1?n. Если Pn-1=(n-1)!, то			друга. Насколько мало? На одну элементарную
	Pn=n!			транспозицию, в которой меняются местами два соседних
4	Нумерация перестановок. Чтобы нумеровать	0		элемента. Возможно ли это? Покажем принципиальную схему
	перестановки, мы отобразим множество Pn			такого алгоритма, нам будет интересна именно она.
	взаимнооднозначно в другое множество Tn, на котором			Представьте себе n-1 элементарных «механизмов», каждый
	ввести нумерацию будет гораздо проще, а затем для			из передвигает свой элемент внутри набора. На каждом
	любого элемента p?Pn в качестве его номера возьмем			шаге механизм делает сдвиг налево или направо.
	номер его образа в Tn. Множество Tn– это прямое			Направление меняется, когда элемент доходит до края. На
	произведение нескольких числовых отрезков Tn			смену направления тратится один шаг, во время которого
	=(0:(n-1))?(0:(n-2)? … ?{0}. Т.е. каждый элемент Tn–			шаг делает следующий механизм, который, впрочем, тоже
	это набор неотрицательных чисел i1, i2, …, in-1, in,			может менять направление.
	причем ik?n-k.		16	Еще алгоритм перебора перестановок -2. Посмотрим	0
5	Отображение. Возьмем перестановку и выпишем рядом с	0		пример. 1 2 3 4 5 Чей ход 1 2 3 4 5 Чей ход a b c d e a
	ней тривиальную перестановку. В качестве первого			c d a b e a b a c d e a c d b a e a b c a d e a c d b e
	индекса возьмем место первого элемента (считая от нуля)			a b b c d a e a c d e b a a b c d e a b c d e a b a c b
	в тривиальной перестановке. Запишем вместо тривиальной			d e a a c d a e b a c b d a e a c a d e b a c b a d e a
	перестановки строку оставшихся символов. В качестве			a c d e b c c a b d e a a d c e b a a c b d e b d a c e
	второго индекса возьмем место второго элемента			b a a c d b e a d c a e b a c a d b e a d c e a b a.
	перестановки в этой строке. Повторим процесс до конца.		17	Перебор перестановок. 1. function	0
	Очевидно, что k–й индекс будет меньше длины k–й строки,			ExistsNextPerm(var kCh: integer): Boolean; var
	а последний индекс будет равен нулю. Посмотрим этот			iV,iP,iVC,iPC: integer; begin result := False; for iV
	процесс на примере.			:= nV downto 2 do if count[iV] < iV-1 then begin
6	Пример отображения. 0 1 2 3 4 5 6 Индекс c a d f g	0		Inc(count[iV]); iP := pos[iV]; iPC := iP+dir[iV]; iVC
	b e a b c d e f g 2 2 a d f g b e a b d e f g 0 2 0 d f			:= perm[iPC]; perm[iP] := iVC; perm[iPC] := iV;
	g b e b d e f g 1 2 0 1 f g b e b e f g 2 2 0 1 2 g b e			pos[iVC] := iP; pos[iV] := iPC; kCh := iP; if dir[iV]
	b e g 2 2 0 1 2 2 b e b e 0 2 0 1 2 2 0 e e 0 2 0 1 2 2			< 0 then Dec(kCh); result := True; exit; end else
	0 0 Очевидно, что этот процесс обратим и обратное			begin count[iV] := 0; dir[iV] := - dir[iV]; end; end;
	отображение построит по набору индексов исходную		18	Задача о минимуме суммы попарных произведений.	0
	перестановку.			Пусть заданы два набора по n чисел, скажем, {ak\|k?1:n}
7	Нумерация множества Tn. Любое прямое произведение	0		и {bk\|k?1:n} . Эти числа разбиваются на пары (ak,bk) и
	упорядоченных множеств можно рассматривать как систему			вычисляется сумма их попарных произведений ?k?1:n akbk.
	счисления с переменным основанием. Вспомните пример с			Можно менять нумерацию {ak} и {bk}. Требуется выбрать
	секундами из первой лекции или рассмотрите какую-либо			такую нумерацию, при которой сумма минимальна. В этой
	старую шкалу размеров: 1 ярд = 3 фута, 1 фут = 12			задаче можно зафиксировать какие-то нумерации {ak} и
	дюймов, 1 дюйм = 12 линий, 1 линия = 6 пунктов. (2, 0,			{bk} и искать перестановку ?, для которой достигается
	4, 2, 3) = 2 ярда 0 футов 4 дюйма 2 линии 3 пункта,			минимум суммы ?k?1:n akb?(k). Мы выберем нумерации,
	сколько же это пунктов? Нужно сосчитать (это называется			когда {ak} расположены по возрастанию, а {bk} – по
	схемой Горнера) (((2 ? 3+0) ? 12+4) ? 12+2) ? 6+3.			убыванию.
8	Нумерация множества Tn - 2. Формулу #, находящую	0	19	Теорема о минимуме суммы попарных произведений.	0
	номер для набора индексов i1, i2, …, in-1, in, мы			Минимум суммы попарных произведений достигается на
	предпочтем написать в виде рекуррентных выражений #(i1,			тривиальной перестановке. Доказательство. Предположим,
	i2, …, in) = a(i1, i2, …, in-1,n-1); a(i1, i2, …, ik,k)			что существуют такие два индекса k и r, что ak < ar
	= a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(пусто,0) = 0; По			и bk < br . В этом случае (ar?ak)(br ?bk) > 0,
	этой формуле #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Имеем			т.е. ar br + ak bk > ar bk + ak br . В нашей
	a(2,1)=2; a(2,0,2) = 2?6+0=12; a(2,0,1,3)=12?5+1=61;			нумерации {ak} расположены по возрастанию. Если {bk}
	a(2,0,1,2,4) =61?4+2=246; a(2,0,1,2,2,5) =246?3+2=740;			расположены не по возрастанию, то найдется такая пара k
	a(2,0,1,2,2,0,6) =740?2+0=1480;			и r, как сказано выше. Переставив у этой пары bk и br ,
9	Перебор наборов индексов. Исходя из	0		мы уменьшим значение суммы. Значит, в оптимальном
	вышеизложенного, перебрать перестановки просто: нужно			решении {bk} стоят по возрастанию. Эта простая теорема
	перебрать все наборы индексов из и по каждому набору			несколько раз встретится нам в дальнейшем.
	строить соответствующую ему перестановку. Для перебора		20	Задача о максимальной возрастающей	0
	наборов индексов заметим, что фактически каждый набор –			подпоследовательности. Задана последовательность
	это запись числа в особой системе счисления с			{ak\|k?1:n} чисел длины n. Требуется найти ее
	переменным основанием (система называется			последовательность наибольшей длины, в которой числа
	факториальной). Правила прибавления 1 в этой системе			{ak} шли бы в возрастающем порядке. Например, в
	почти так же просты, как в двоичной: двигаясь от			последовательности 3, 2, 11, 14, 32, 16, 6, 17, 25, 13,
	последнего разряда пытаться прибавить в текущем разряде			37, 19, 41, 12, 7, 9 максимальной будет
	1. Если это возможно, то прибавив 1 остановиться. Если			подпоследовательность 2, 11, 14, 16, 17, 25, 37, 41 С
	невозможно, записать в разряд нуль и перейти к			перестановками эта задача связана тем, что исходная
	следующему разряду.			последовательность может быть перестановкой. Мы
10	Перебор наборов индексов - 2. Рассмотрим пример: 7	0		ограничимся тем, что покажем, как решается эта задача,
	6 5 4 3 2 1 Это переменные основания 3 4 4 2 1 1 0 3 4			а формализацию и обоснование алгоритма предоставим
	4 2 2 0 0 Обратите внимание, что в 3 4 4 2 2 1 0 каждой			слушателям.
	строке начало такое 3 4 4 3 0 0 0 же, как в предыдущей,		21	Нахождение максимальной возрастающей	0
	3 4 4 3 0 1 0 затем идет элемент, строго 3 4 4 3 1 0 0			подпоследовательности. Будем по возможности экономно
	больший, . . . , а 3 4 4 3 1 1 0 дальнейшее не			разбивать нашу на убывающие последовательности (пример
	существенно. 3 4 4 3 2 0 0 Значит, каждая строка 3 4 4			изменен) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6
	3 2 1 0 лексикографически больше 3 5 0 0 0 0 0			5 12 11 8 7 14 13 18 16 15 17 37 19 21 Каждое следующее
	предыдущей. 3 5 0 0 0 1 0.			число пишется в самую верхнюю из строчек, где оно не
11	Теорема о лексикографическом переборе перестановок.	0		нарушит порядка. Возьмем число из нижней строчки, 21.
	Описанный алгоритм перебирает перестановки в порядке			Почему оно стоит в 8-й строчке? Ему мешает 19. А числу
	лексикографического возрастания. Доказательство. Нам			19 мешает 17. А ему 16. И т. д. Последовательность 9,
	достаточно показать, что если мы имеем два набора			11, 14, 16, 17, 19, 21 возрастает и имеет длину 7.
	индексов I1 и I2, и I1 лексикографически предшествует			Любая последовательность большей длины содержит два
	I2, то перестановка ?(I1) лексикографически			числа из одной строки (принцип Дирихле) и не может быть
	предшествует ?(I2). Эти перестановки формируются			возрастающей.
	последовательно, и пока совпадают I1 и I2, совпадают и		22	Задача о минимальном числе инверсий. Задана	0
	их перестановки. А большему значению индекса			последовательность {ak\|k?1:n} чисел длины n. Инверсией
	соответствует и больший элемент.			назовем выполняемое на месте зеркальное отражение
12	Прямой алгоритм лексикографического перебора	0		какой-либо ее подстроки – сплошной
	перестановок. Возьмем какую-либо перестановку p и прямо			подпоследовательности.Требуется за минимальное число
	найдем лексикографически следующую. Возьмем начало –			инверсий расположить элементы последовательности по
	первые k элементов. Среди его продолжений известны			возрастанию. Например, перестановку «сплошная» можно
	минимальное, в котором все элементы расположены по			преобразовывать так (красные буквы переставлены,
	возрастанию, и максимальное, в котором по убыванию.			большие уже стоят на месте) сплошнаЯ сплоанШЯ наолПСШЯ
	Например, в перестановке p =(4, 2, 1, 7, 3, 6, 5) все			АнолПСШЯ АнлОПСШЯ АЛНОПСШЯ (за пять инверсий).
	продолжения для (4, 2, 1) лежат между (3, 5, 6, 7) и		23	Экзаменационные вопросы. Перестановки. Их перебор и	0
	(7, 6, 5, 3). Имеющееся продолжение меньше			нумерация. Задача о минимуме скалярного произведения.
	максимального, и 3-й элемент еще можно не менять. И 4-й			Задача о наибольшей возрастающей подпоследовательности.
	тоже. А 5-й нужно сменить. Для этого из оставшихся		24	Задание. 1. Двусторонний переход перестановка ?	0
	элементов нужно взять следующий по порядку, поставить			число 2. Найти перестановку, отстоящую от данной на
	его 5-м и приписать минимальное продолжение. Получится			данное число шагов. 3. Перебор перестановок
	(4, 2, 1, 7, 5, 3, 6).			элементарными транспозициями. 4. Выполнить пример для
13	Прямой алгоритм лексикографического перебора	0		задачи о минимуме скалярного произведения.
24	«Перестановки элементов» \| Комбинаторика				0