Перестановки

8. Перестановки

Перестановками множества {a1, a2, …, an} называются расположения этого множества в различном порядке [1]. Перестановка определяется последовательностью индексов располагаемых элементов, поэтому можно считать, что переставляются числа {1, 2, …, n}. Число n считается порядком перестановки. Всего имеется n! различных перестановок порядка n.

Есть разные способы представления перестановок. Простейший из них – указание последовательности чисел перестановки, например (2, 4, 1, 5, 3). Иногда удобно записывать перестановку в 2 строки, где первая задает места элементов, а вторая сами элементы, например

  1,  2, 3, 4, 5

2, 4, 1, 5, 3

Если поменять строки местами и упорядочить столбцы по возрастанию чисел в первой строке, то получим перестановку, называемую обратной. Для перестановки A обратная перестановка обозначается A-1. В приведенном примере обратной будет перестановка

  1,  2, 3, 4, 5

3, 1, 5, 2, 4

Произведение перестановок C = A×B определяется следующим образом. Если в перестановке A на месте i находится элемент j, а в перестановке B на месте j  элемент k, то в произведении C на месте i окажется k. Например,

  1,  2, 3, 4, 5  ×  1, 2, 3, 4, 5  =  1, 2, 3, 4, 5

2, 4, 5, 3, 1  5, 3, 1, 2, 4  3, 2, 4, 1, 5

Произведение перестановок некоммутативно, то есть A×B ≠  B×A.

Единичной называется перестановка (1, 2, …, n). Произведение любой перестановки на единичную как справа, так и слева не меняет ее, а произведение перестановки на обратную дает единичную перестановку. Таким образом, множество перестановок определенного порядка образуют группу.

В группе перестановок можно решить, например уравнение A×X = B, где A и B – заданные перестановки. Умножая обе части уравнения слева на A-1, получим X = B×A-1.

Распространенными задачами для перестановок являются генерация всех перестановок в определенном порядке и выбор случайной перестановки с равной вероятностью.

Начнем с задачи перечисления всех перестановок в лексикографическом порядке. Перестановка (б1, б2, …, бn) лексикографически меньше перестановки (в1, в2, …, вn), если бi = вi  при i = 1, …, k и бi < вi  при i = k + 1. Лексикографический порядок называют иногда алфавитным. Действительно, именно такой принцип лежит в основе расположения слов по алфавиту. Например, при n = 3 в лексикографическом порядке следуют перестановки (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Если рассматривать эти перестановки как трехзначные числа, то лексикографический  порядок совпадает с расположением чисел по возрастанию.

Приведем алгоритм перечисления перестановок порядка n в лексикографическом  порядке.

Выбор начальной перестановки р = (р1, р2, …, рn) = (1, 2, …, n). Выдача перестановки р. Просмотр перестановки р справа налево. Поиск самой правой позиции i такой, что рi< рi+1. Если это невозможно, то конец перебора (выдана последняя наибольшая перестановка). Поиск рj – наименьшего элемента справа от рi такого, что рj> рi. Транспозиция (обмен) элементов рj и рi. В результате рi+1 > рi+2 > …> рn. Начиная с позиции i+1 изменение элементов перестановки на рn, рn-1,…, рi+1. Переход к 2.

Пусть, например, последняя выданная перестановка р = (2, 6, 5, 8, 7, 4, 3, 1). Здесь n =8, i = 3 и рi =5, j = 5 и рj =7. После транспозиции элементов рj и рi  получается перестановка (2, 6, 7, 8, 5, 4, 3, 1), а после изменения мест конечных элементов приходим к следующей в лексикографическом порядке перестановке (2, 6, 7, 1, 3, 4, 5, 8).

Если перечислять перестановки порядка 5 с самого начала, то последовательно получим перестановки (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3) и т. д.

Можно рекурсивно определить точное соответствие между целыми числами 0, 1, …, n!-1 и перестановками из множества {1, 2, …, n}, записанными в лексикографическом порядке [1].

Другой способ перечисления перестановок основан на векторах инверсий. Пусть X = (x1, x2, …, xn) – некоторая перестановка элементов 1, 2, …, n. Пара (xi, xj)  называется инверсией, если  i < j,  а  xi > xj.  Например, в перестановке (5, 2, 1, 3, 4) имеются инверсии (5, 2), (5, 1), (5, 3), (5, 4), (2, 1). Вектором инверсий называют упорядоченное множество D = (d1, d2, …, dn), где dj – количество элементов xi таких, что пара (xi, xj) является инверсией. Иными словами dj - это число элементов, больших xj и стоящих в перестановке X слева от xj. Очевидно, что d1 = 0 и 0 ≤ dj < j.

Вектор инверсий однозначно определяется по перестановке. Например, для  перестановки X = (5, 2, 1, 3, 4) вектор инверсий D = (0, 1, 2, 1, 1).

С другой стороны, по корректному вектору инверсий однозначно восстанавливается перестановка. Пусть, например, D = (0, 1, 2, 1, 1). Будем рассматривать компоненты вектора инверсий справа налево. Поскольку d5 = 1, то из чисел 1, 2, 3, 4, 5 лишь одно больше величины x5. Значит, x5 = 4. Так как d5 = 0,  то из оставшихся чисел 1, 2, 3, 5 на предпоследнем месте стоит наибольшее из них, то есть 5. Значение d3 = 2 указывает, что среди чисел 1, 2, 3 в середине должно стоять третье по величине, то есть 1. В результате приходим к исходной перестановке X = (5, 2, 1, 3, 4). Таким образом, существует взаимно-однозначное соответствие (изоморфизм) между перестановками и векторами инверсий.

Желательно, чтобы при перечислении соседние перестановки отличались как можно меньше. Минимальное различие может выражаться в транспозиции или обмене каких-либо двух соседних элементов перестановки.

Такую последовательность перестановок можно построить рекурсивно. При n = 1 единственная перестановка, очевидно,  удовлетворяет требованиям. Предположим, что мы имеем последовательность П1, П2, … перестановок на множестве {1, 2, …, n-1}, в которой последовательные перестановки различаются только транспозицией смежных элементов. Мы будем расширять каждую из этих (n-1)! перестановок,  вставляя элемент n на каждое из n возможных мест следующим образом: n добавляется к Пi последовательно во все позиции справа налево, если i нечетно, и слева направо, если i четно. Порядок порождаемых таким образом перестановок будет следующим:

1234

  123  1243

1423

4123

4132

12  132  1432

1342

1324

3124

312  3142

3412

1  4312

4321

321  3421

3241

3214

2314

21  231  2341

2431

4231

4213

213  2413

2143

2134

Имея какой-либо способ нумерации перестановок порядка n, легко получить случайную перестановку, ставя ее в соответствие случайному целому числу из диапазона от 0 до n! -1. Например, это можно сделать на основе лексикографического порядка перечисления перестановок. Существует вариант нумерации перестановок с помощью векторов инверсий [1]. Оба эти способа приводят к вычислительным трудностям при нахождении больших целых чисел.

Эффективный метод порождения случайных перестановок осуществляют последовательности из n-1 случайных транспозиций. Начиная с любой перестановки (р1, р2, …, рn), элемент рn переставляется с одним из элементов р1, р2, …, рn,  выбираемым случайно. Затем рn-1 меняется местами с одним из элементов р1, р2, …, рn-1, выбираемым случайно и т. д.

Для того, чтобы показать, что все n! перестановок равновероятны, воспользуемся индукцией. Для n = 1 результат очевиден. Предположим, что алгоритм порождает случайные перестановки для n = k, то есть вероятность получения любой перестановки  из k элементов составляет 1/k! Пусть при n=k+1 получена перестановка П=(р1, р2, …, рk+1), в которой элемент k+1 оказался на месте j (1 ≤ j ≤ k+1). Поскольку на любом из этих k+1 мест элемент k+1 может быть в соответствии с алгоритмом с равной вероятностью, то вероятность перестановки

P(П) = P(р1, р2, …, рj-1, k+1, рj+1,…, рk+1) = (1/k!) ×P(р1, р2, …, рj-1, рj+1,…, рk+1)=

=(1/k!) ×1/(k+1) = 1/(k+1)!

Следовательно, утверждение справедливо при n = k+1, то есть алгоритм порождает любую перестановку с равной вероятностью.

Задачи для самостоятельного решения

8.1. Слова (3)

Дана строка, состоящая из M символов. Вывести все перестановки символов данной строки.

Ввод из файла INPUT. TXT. В первой строке файла находится исходная строка.

Вывод в файл OUTPUT. TXT. Вывести в каждой строке файла по одной перестановке.

Ограничения: 2 ≤ M ≤ 9, символы – строчные буквы и цифры, время 1 с.
Перестановки можно выводить в любом порядке. Повторений и строк, не являющихся перестановками исходной, быть не должно.

Примеры

Ввод 1  Ввод 2

AB  122

Вывод 1  Вывод 2

AB  122

BA  212

  221

Простые примеры на перестановки (6)

Составить программы для решения следующих задач:

решить уравнение на перестановках вида A×X = B,  где A и B - заданные перестановки, а X - неизвестная перестановка; по заданной перестановке из N элементов выдать K следующих перестановок в лексикографическом порядке; по заданной перестановке построить вектор  инверсий, а по вектору инверсий восстановить перестановку; перечислить перестановки из N элементов путем транспозиции смежных элементов с рекурсией и без нее.

Входные данные задавать с клавиатуры, вывод результатов - на экран.

8.3. Матрица (8)

В матрице A размера N×N числа от 1 до N2. Каждое число записано ровно один раз. Даны две матрицы размера N×N: Top и Left. Значение Topi j определяет количество чисел, больших Ai j и расположенных выше по столбцу, Lefti j - количество чисел, больших Ai j и расположенных левее по строке. Найти возможные значения матрицы A. Если решений несколько, вывести любое.

Ввод из файла INPUT. TXT. В первой строке N (1 ≤ N ≤100), затем N строк матрицы Top (числа через пробел), затем N строк матрицы Left. Числа в обеих матрицах от 0 до N.

Вывод в файл OUTPUT. TXT матрицы A – N строк, числа в строке через пробел. Если решений нет, вывести 0.

Пример

Ввод

3 

0 0 0

0 0 0

0 0 2

0 0 0

0 1 0

0 1 2

Вывод

1 2 6

5 3 7

9 8 4

Подсказка. Основной принцип – проставлять очередное число в цикле от 1 до N2 в такую клетку (i, j), где i –номер строки, а  j – номер столбца, значение которой должно быть наименьшим среди незаполненных клеток строки i и столбца j. Это свойство нужно уметь проверять по  матрицам Top и Left. Тогда заполненная матрица не будет противоречить заданным условиям. Различных решений может быть много.

8.4. Перестановки (9)

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется  написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

Ввод из файла INPUT. TXT. В первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

Вывод. В выходной файл OUTPUT. TXT необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры

Ввод 1  Ввод 2  Ввод 3

4 1 2  4 4 2  4 5 2

6 8 3 9  6 8 3 9  6 8 3 9

Вывод 1  Вывод 2  Вывод 3

3 9 6 8  9 3 6 8  -1

Подсказка. Для сокращения вычислений стоит заранее по алгоритму Евклида [4] найти наибольший общий делитель по всем парам чисел. Полное решение данной задачи основано на использовании динамического программирования и эффективном кодировании подмножества исходного множества. В качестве подзадач здесь следует рассматривать задачи, аналогичные исходной, но для некоторого подмножества исходного множества чисел. Выберем в качестве состояния пару из подмножества P исходного множества S и номера выделенного элемента j в нем. Для каждого состояния будем хранить количество существующих k–перестановок из элементов данного подмножества P, но только таких перестановок, в которых последний элемент имеет номер j (в исходной нумерации). Начальное состояние в этом случае будет P=Ш. При программной реализации подмножество P удобно хранить с помощью битовых масок.

Рекуррентные формулы для переходов можно представить на основе того, что к множеству можно добавить элемент, который в нем не содержится. Реализация перехода не представляет особых трудностей. Единственное, о чем необходимо помнить, – после заполнения таблицы динамического программирования требуется выполнить восстановление ответа, последовательно определяя, какое число поставить на очередную позицию.

Описанные алгоритм имеет время работы O(m22m). Несмотря на то, что данное решение работает за экспоненциальное время, оно значительно быстрее простого перебора.

9. Подмножества множеств

Пусть имеется множество A={a1, a2, …, an}. Имеется 2n подмножеств этого множества. Действительно, каждый из элементов независимо от других может как входить, так и не входить в подмножество.

Порождение всех подмножеств эквивалентно порождению всех n-разрядных двоичных наборов: ai принадлежит подмножеству множества A тогда и только тогда, когда i-й разряд равен 1. В свою очередь задача порождения случайного подмножества сводится к задаче порождения случайного двоичного набора длины n, то есть случайного числа в диапазоне от 0 до 2n – 1.

Наиболее очевидным способом порождения всех двоичных наборов длины n  является счет в системе счисления с основанием 2. При этом два последовательных подмножества могут значительно отличаться друг от друга количеством и составом элементов, что соответствует появлению старшего разряда в очередном двоичном числе.

Рассмотрим следующую задачу.

Дипломатия. На дипломатический раут в специально оборудованном помещении собрались представители N держав. Организаторы встречи знают, что ряд вопросов должен обсуждаться в узком кругу участников. Некоторые документы могут готовиться представителем единственной страны. В то же время ряд решений принимается без участия представителя какой-либо страны (например, последствия ядерной программы Ирана могут обсуждаться без представителя Ирана). Не владея всеми тайнами дипломатии, организаторы решили обеспечить всевозможные сочетания участников встречи, вызывая некоторых дипломатов в другое помещение для оформления пропусков и возвращая их обратно. Необходимо вызывать и возвращать дипломатов по одному человеку, в противном случае может возникнуть дипломатический скандал. Помогите организаторам справиться с этой проблемой.

Эта задача решается путем использования кодов Грея. Наименьшим возможным изменением при переходе от одного подмножества к другому является добавление или удаление одного элемента множества. В терминах двоичных наборов это означает, что последовательные наборы должны различаться в одном разряде. Такие последовательности двоичных наборов называются кодами Грея. Более точно: n-разрядный код Грея есть упорядоченная циклическая последовательность  из 2n n-разрядных наборов (кодовых слов), такая, что последовательные кодовые слова различаются в одном разряде. Обычно начальным кодовым словом считают (0, 0,…, 0), хотя на самом деле это несущественно, поскольку код циклический.

Существует много n-разрядных кодов Грея. Рассмотрим один из них. Предположим, что

G0

G1

G(n) =  …

GM  ,

где M = 2n - 1, есть n-разрядный код Грея, записанный в виде матрицы  2n × n так, что i-я строка матрицы является i-м кодовым словом. Тогда

  0G0

  0G1

…

  0GM

G(n+1) =  1GM

1GM-1

  …

1G1

1G0

очевидно, есть (n+1)-разрядный код Грея. По этому рекурсивному определению

G(1) =  0

  1

00

G(2) =  01

  11

  10

000

  001

  011

G(3) =  010

110

111

101

100

Можно определить (n+1)-разрядный код Грея иначе:

  G00

  G01

  G11

G(n+1) =  G10

  G20

  G21

…

  …

Легко проверить, что таким образом получается тот же самый код Грея. Этот способ позволяет найти правило получения следующего слова кода Грея порядка N из предыдущего. Будем считать, что слово, состоящее из одних нулей, имеет нулевой номер. Далее если предыдущее слово имеет четный номер, то надо инвертировать на противоположный последний бит. Для нечетного номера инвертируется бит, находящийся слева от самой правой единицы слова.

Для перечисления слов Грея целесообразно организовать стек из номеров позиций текущего слова Грея, в которых находится 1, в порядке просмотра справа налево. В вершине стека будет номер позиции первой 1 справа, далее – номер второй позиции с 1 и т. д. При переходе от слова с четным номером к последующему при изменении последнего разряда с 0 на 1 вершиной стека становится номер первой позиции, в противном случае этот номер удаляется из вершины стека. В случае нечетного номера слова в вершине стека находится позиция S первой единицы справа. На следующем слове либо в стек перед его вершиной включается номер S + 1, либо этот номер удаляется из стека.

Приведенное рекурсивное определение близко к рекурсивному определению двоичного представления целых чисел. Действительно, если

  0  B0

  1  B1

  2  B2

  …  =  …

  …  …

  2n -1  BM

то

  0  B00

  1  B01

  2  B10

  3  =  B11

  …  …

  2n+1 -2  BM0

  2n+1 -1  BM1

Это позволяет предложить способ получения Gi из двоичного представления числа i. Если

  i = (bn bn-1 …b0)2,

то

Gi = (gn gn-1 …g1)2, 

где

gj = bj + bj-1  (mod 2),  1 ≤ j ≤ n.

Последнее равенство дает возможность вычислить номер кодового слова Gi по его представлению. Пусть i = (bn bn-1 …b0)2. Тогда

  n

bj = У gm (mod 2), 1 ≤ j ≤ n.

  m=j+1

Сложение двух разрядов по модулю 2 то же самое, что исключающее “или” (XOR), поэтому можно просто сдвинуть разряды i на одну позицию влево и выполнить операцию исключающего “или”:

bn  bn-1  … b2  b1  b0

bn  bn-1  bn-2…  b1  b0

gn  gn-1  … g2  g1

Приведенные формулы позволяют перечислить нерекурсивно кодовые слова Грея заданной размерности n, изменяя i от 0 до 2n –1 и получая по двоичному представлению i разряды кодового слова Gi. Аналогично, если взять случайное число i в диапазоне от 0 до 2n –1, то по нему легко восстанавливается случайное кодовое слово Gi.

Пусть, например, n = 3, а i = 5 = (0101)2. Тогда операция XOR дает:

0  1  0  1

  0 1  0  1

  1  1  1  ,

что соответствует кодовому слову G5. В качестве проверки выполним обратное преобразование разрядов кодового слова G5 в двоичные разряды i, в результате которого получим i = (0101)2 = 5.

Коды Грея используются в комбинаторике, криптографии, задачах дискретной оптимизации и многих других областях.

Рассмотрим еще одну распространенную задачу. Пусть задано множество {a1, a2, …, an}. Рассмотрим порождение в лексикографическом порядке подмножеств из k элементов, то есть сочетаний из n предметов по k штук. Как и ранее можно считать, что подмножество определяется последовательностью индексов располагаемых элементов, поэтому будем выбирать подмножества множества {1, 2, …, n}.

Например, трехэлементные подмножества множества {1, 2, 3, 4, 5, 6} записываются в лексикографическом порядке следующим образом:

123  135  234  256

124  136  235  345

125  145  236  346

126  146  245  356 

134  156  246  456

Подмножества или сочетания в лексикографическом порядке можно порождать простым способом. Начиная с сочетания (1, 2, …, k) следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который еще не достиг максимального значения. Этот элемент увеличивается на 1. Всем элементам справа от него присваиваются новые наименьшие возможные значения, которые должны быть больше данного элемента.

Задачи для самостоятельного решения

9.1. Простые примеры на подмножества (4)

Составить программы для решения следующих задач:

выдать слова кода Грея заданной размерности, используя рекурсию и генерацию слов по их номерам; задано множество символов, выдать его подмножества из заданного числа элементов в лексикографическом порядке;

Входные данные задавать с клавиатуры, вывод результатов - на экран.

9.2. Простоватые числа (4)

Студент Вася отыскивает простые числа в диапазоне от 1 до N (1 ≤ N ≤ 109). Если число M, не превосходящее N, не делится на  2, 3 и 5, Вася называет его “простоватым”. По заданному значению N найти количество простоватых чисел.

Ввод. В единственной строке файла INPUT. TXT находится число N.

Вывод. В единственную строку файла OUTPUT. TXT вывести количество простоватых чисел.

Пример

Ввод

10

Вывод

2