Лекция 1_03: Комбинаторика. Перестановки

Предмет лекции

Пусть задано некое конечное множество A из n элементов.

Любое упорядочение этих элементов, т. е. расположение их в какой-либо последовательности, называется перестановкой. Иногда добавляют «из n элементов». Обычно выделяется одно, основное или естественное, упорядочение, которое называется тривиальной перестановкой.

Сами элементы множества A нас не интересуют. Часто в качестве рассматриваемых элементов берут целые числа от 1 до n или от 0 до n−1.

Обозначим множество перестановок из n элементов через P_n, а его мощность через P_n.

Зададим знакомые нам уже три вопроса: чему равно P_n, как перебрать элементы P_n, как их перенумеровать.

Теорема о числе перестановок

Теорема. Число перестановок из n элементов равно n! — произведению чисел от 1 до n.

(Обозначение n! читается эн-факториал.)

Доказательство. По индукции. Для n = 1 формула очевидно верна.

Пусть она верна для n − 1, докажем, что она верна и для n. Первый элемент упорядочения можно выбрать n способами, а к выбранному первому элементу можно P_n−1 способами приписать остальное. Поэтому верна формула P_n = n × P_n−1.
Если P_n−1 = (n−1)!, то P_n = (n)!

Нумерация перестановок

Для нумерования перестановки, мы отобразим множество P_n взаимнооднозначно (построим биекцию) в другое множество T_n, на котором ввести нумерацию будет гораздо проще, а затем для любого элемента p ∈ P_n в качестве его номера возьмем номер его образа в T_n.

Множество T_n — это прямое произведение нескольких числовых отрезков

T_n = 0:(n−1) ´ 0:(n−2) ´ … ´ {0}.

Таким образом, каждый элемент T_n — это набор неотрицательных чисел i₁, i₂, …, i_n−1, i_n,
причем i_k £ n−k.

Итак, строим отображение.

Возьмем перестановку и выпишем рядом с ней тривиальную перестановку. В качестве первого индекса возьмем место первого элемента (считая от нуля) в тривиальной перестановке. Запишем вместо тривиальной перестановки строку оставшихся символов. В качестве второго индекса возьмем место второго элемента перестановки в этой строке. Повторим процесс до конца.

Очевидно, что k–й индекс будет меньше длины k–й строки, а последний индекс будет равен нулю.

Посмотрим этот процесс на примере.

Пример отображения

	0 1 2 3 4 5 6		0 1 2 3 4 5 6		Индекс
	c a d f g 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 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		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 0

Очевидно, что этот процесс обратим и что обратное отображение построит по набору индексов исходную перестановку.

Нумерация множества T_n

Любое прямое произведение упорядоченных множеств можно рассматривать как систему счисления с переменным основанием. Вспомните пример с секундами из первой лекции или рассмотрите какую-либо старую шкалу размеров:

1 ярд = 3 фута,
1 фут = 12 дюймов,
1 дюйм = 12 линий,
1 линия = 6 пунктов.

(2, 0, 4, 2, 3) = 2 ярда 0 футов 4 дюйма 2 линии 3 пункта, сколько же это пунктов?

Нужно вычислить (это называется схемой Горнера) (((2 ´ 3+0) ´ 12+4) ´ 12+2) ´ 6+3.

Формулу #, сопоставляющую набору индексов i₁, i₂, …, i_n−1, i_n его номер, мы предпочтем написать в виде рекуррентных выражений

#(i₁, i₂, …, i_n−1, i_n) = a(i₁, i₂, …, i_n−1, n−1),
a(i₁, i₂, …, i_k, k) = a(i₁, i₂, …, i_k−1, k−1)(n−k+1)+ i_k,
a(пусто,0) = 0.

По этой формуле #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6).

Далее имеем

a(2,1) = 2;
a(2,0,2) = 2 ´ 6+0=12;
a(2,0,1,3) = 12 ´ 5 + 1 = 61;
a(2,0,1,2,4) = 61 ´ 4 + 2 = 246;
a(2,0,1,2,2,5) = 246 ´ 3 + 2 = 740;
a(2,0,1,2,2,0,6) = 740 ´ 2 + 0 = 1480;

Исходя из вышеизложенного, перебрать перестановки просто: нужно перебрать все наборы индексов из T_n, строя по каждому набору соответствующую ему перестановку.

Для перебора наборов индексов заметим, что фактически каждый набор — это запись числа в особой системе счисления с переменным основанием (система называется факториальной).

Правила прибавления 1 в этой системе почти так же просты, как в двоичной: двигаясь от последнего разряда пытаться прибавить в текущем разряде 1. Если это возможно, то прибавив 1 остановиться. Если невозможно, записать в разряд нуль и перейти к следующему разряду.

Пример

Рассмотрим пример перебора чисел в факториальной записи, начиная с какого-нибудь значения:

7 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 В третьем разряде

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 3 2 1 0 В первом разряде

3 5 0 0 0 0 0 В пятом разряде

В каждой строке начало такое же, как в предыдущей, затем идет элемент, строго больший, . . . , а дальнейшее не существенно. Значит, каждая строка лексикографически больше предыдущей.

Теорема о лексикографическом переборе перестановок

Теорема. Описанный алгоритм перебирает перестановки в порядке лексикографического возрастания.

Доказательство. Нам достаточно показать, что если мы имеем два набора индексов N₁ и N₂, и N₁ лексикографически предшествует N₂, то перестановка π(N₁) лексикографически предшествует π(N₂).

Эти перестановки формируются последовательно, и пока совпадают N₁ и N₂, совпадают и их перестановки. А большему значению индекса соответствует и больший элемент.

Прямой алгоритм лексикографического перебора перестановок

Можно организовать лексикографический перебор перестановок и непосредственно. Нам будет полезно в этой возможности разобраться.

Возьмем какую-либо перестановку π и прямо найдем лексикографически следующую.

Возьмем начало перестановки — первые k элементов. Среди его продолжений известны лексикографически минимальное, в котором все оставшиеся элементы расположены по возрастанию, и максимальное, в котором они расположены по убыванию.

Например, в перестановке π = (4, 2, 1, 7, 3, 6, 5) все продолжения для (4, 2, 1) лежат между (3, 5, 6, 7) и (7, 6, 5, 3).

Какая же перестановка будет следующей за π = (4, 2, 1, 7, 3, 6, 5)? Мы должны выбрать как можно большее начало, которое можно сохранить. Имеющееся продолжение начала (4, 2, 1) меньше максимального, и 3-й элемент еще можно не менять. И 4-й тоже. А 5-й сохранить невозможно и нужно сменить.

Для этого из оставшихся элементов нужно взять следующий по порядку, поставить его пятым и приписать минимальное продолжение. Получится (4, 2, 1, 7, 5, 3, 6).

Выпишем несколько следующих перестановок. В зеленый цвет выкрашена не меняющаяся часть (префиксная часть, она стоит в начале), красный — меняющийся элемент, черный — остаток, расположенный по убыванию.
(4 2 1 7 5 3 6)
(4 2 1 7 5 6 3)
(4 2 1 7 6 3 5)
(4 2 1 7 6 5 3)
(4 2 3 1 5 6 7)
(4 2 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)
можете продолжить этот процесс сами.

Формальное описание алгоритма перебора перестановок

Рабочее состояние: Перестановка π и булевская переменная IsActive.

Начальное состояние: В π записана тривиальная перестановка и IsActive истинно.

Стандартный шаг: Если IsActive , выдать перестановку в качестве результата. Двигаясь с конца, найти в перестановке наибольший монотонно убывающий суффикс. Пусть k — позиция перед суффиксом.

Положить IsActive := (k > 0). Если IsActive, то найти в суффиксе наименьший элемент, превосходящий π_k, поменять его местами с π_k, а потом суффикс «перевернуть» (как это делалось во встречавшейся нам процедуре mirror).

Перебор перестановок мелкими изменениями

Как и в случае 0-1-наборов, интересно иметь способ перебора перестановок, при котором на каждом переходе перестановка меняется по возможности мало. Таким малым изменением здесь может служить элементарная транспозиция — изменение порядка двух соседних элементов. Возможен ли такой перебор? Покажем его принципиальную схему, нам будет интересна именно она.

Представиме себе n−1 элементарных «механизмов», сопоставленных всем, кроме одного элементам множества. Каждый механизм передвигает «свой» элемент внутри набора. На каждом шаге механизм делает сдвиг налево или направо. Направление меняется, когда элемент доходит до края. На смену направления тратится один шаг, во время которого шаг делает следующий механизм, который, впрочем, точно так же может менять свое направление сдвига. Смена направления у последнего механизма завершает процесс перебора.

Рассмотрим пример
     (a b c d e) шаг механизма a
     (b a c d e) шаг механизма a
     (b c a d e) шаг механизма a
     (b c d a e) шаг механизма a
     (b c d e a) смена направления a   шаг механизма b
     (c b d e a) шаг механизма a
     (c b d a e) шаг механизма a
     (c b a d e) шаг механизма a
     (c a b d e) шаг механизма a
     (a c b d e) смена направления a   шаг механизма b
     (a c d b e) шаг механизма a
     (c a d b e) шаг механизма a
     (c d a b e) шаг механизма a
     (c d b a e) шаг механизма a
     (c d b e a) смена направления a   шаг механизма b
     (c d e b a) смена направления b   шаг механизма c
     (d c e b a) шаг механизма a
и так далее.

Этот алгоритм удивительно легко программируется

  function 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
        Inc(count[iV]); iP := pos[iV];
        iPC := iP+dir[iV]; iVC := perm[iPC];
        perm[iP] := iVC; perm[iPC] := iV;
        pos[iVC] := iP; pos[iV] := iPC;
        kCh := iP; if dir[iV] < 0 then Dec(kCh);
        result := True; exit;
      end else begin
        count[iV] := 0; dir[iV] := − dir[iV];
      end;
  end;

Есть два массива, которые каждому механизму i сопоставляют два числа dir[i] — приращение шага (изменяющее направление) и count[i] — счетчик тактов. Просматриваются все механизмы и у тех, где счетчик дошел до верхнего предела он обнуляется, а направление изменяется. Когда встречается механизм, не дошедший до предела, он выполняет один шаг и прекращает цикл.

Экстремальные задачи, связанные с перестановками

В заключение рассмотрим несколько неожиданных экстремальных задач, которые связаны с перестановками. Они окажутся полезными для нас в дальнейшем.

Задача о минимуме суммы попарных произведений

Пусть заданы два набора по n чисел, скажем, {a_k | k ∈ 1:n} и {b_k | k ∈ 1:n}. Эти числа разбиваются на пары (a_k, b_k) и вычисляется сумма попарных произведений чисел в этих парах Σ_k a_kb_k. Можно менять нумерацию элементов (a_k и b_k).

Требуется выбрать такую нумерацию, при которой сумма минимальна.

В этой задаче можно зафиксировать какие-то нумерации a_k и b_k и искать перестановку π, для которой достигается минимум суммы Σ_k a_kb_π(k). Выберем в качестве основных нумерации, когда a_k расположены по возрастанию, а b_k — по убыванию.

Теорема о минимуме суммы попарных произведений

Теорема. Минимум суммы попарных произведений достигается на тривиальной перестановке.

Доказательство. Предположим, что существуют такие два индекса k и r, что a_k < a_r и b_k < b_r. В этом случае

(a_r−a_k) (b_r−b_k) > 0, т.е. a_rb_r + a_kb_k > a_rb_k + a_kb_r.

В нашей нумерации {a_k} расположены по возрастанию. Если {b_k} расположены не по возрастанию, то найдется пара k и r, с описанными выше свойствами. Переставив у этой пары b_k и b_r, мы уменьшим значение суммы. Значит, в оптимальном решении {b_k} стоят по возрастанию.

Эта простая теорема несколько раз понадобится нам в дальнейшем.

Задача о максимальной возрастающей подпоследовательности

Задана последовательность чисел {a_k | k ∈ 1:n} длины n. Требуется найти ее подпоследовательность наибольшей длины, в которой числа {a_k} шли бы в возрастающем порядке.

Например, в последовательности

3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9

максимальной будет подпоследовательность красных чисел.

С перестановками эта задача связана тем, что исходная последовательность может быть перестановкой.

Мы ограничимся тем, что покажем, как решается эта задача, на примере, а формализацию и обоснование алгоритма предоставим слушателям.
Возьмем новую последовательность, а по ней построим таблицу
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
25 14 11 33 27 29 41 15 26 32 54 87 83 15 77 91 16 35 44 23 35 37 38 12 20 29
Исходная последовательность разбивается на строчки по возможности экономно: Каждое следующее число пишется в самую верхнюю из строчек, где оно не нарушит порядка. Возьмем число из нижней строчки, 91. Почему оно стоит в 8-й строчке? Ему мешает 77, уже стоящее в 7-й строчке. А числу 77 мешает 54. А ему 32. И т. д.

Последовательность 11, 15, 26, 32, 54, 77, 91 возрастает и имеет длину 7.

Любая последовательность большей длины содержит два числа из одной строки (принцип Дирихле, у нас появился повод назвать еще одного крупного математика, «отметившегося» в дискретной математике — Лежён Дирихле (1805-1859)) и не может быть возрастающей.

Задача о минимальном числе инверсий

Задана последовательность чисел {a_k | k ∈ 1:n} длины n. Инверсией назовем выполняемое на месте зеркальное отражение какой-либо ее подстроки — сплошной подпоследовательности. Требуется за минимальное число инверсий расположить элементы последовательности по возрастанию.

Например, перестановку «сплошная» можно преобразовывать так (красные буквы будут на данной итерации переставлены, большие уже стоят на месте)
    сплошнаЯ
    сплоанШЯ
    наолПСШЯ
    АнолПСШЯ
    АнлОПСШЯ
    АЛНОПСШЯ
(справились за пять инверсий)

Упражнения

Найдите номер перестановки ВЕРБЛЮД при нулевой перестановке БВДЕЛРЮ.

Напишите 10 перестановок, лексикографически следующих после перестановки ЭМБРИОН.

Выпишите перестановку номер 15783 (считая от 0) из букв предыдущего примера.

Экзаменационные вопросы

Перестановки. Их перебор и нумерация.

Задача о минимуме скалярного произведения.