Генерация перестановок без повторений

Листал я недавно книгу Никлауса Вирта "Алгоритмы и структуры данных" 2010-го года издания и наткнулся на задачу для самостоятельного решения, в которой предлагалось написать процедуру порождения всех перестановок из n элементов. Машинально я отметил эту задачу как простую и, по этой причине, неинтересную. А потом вдруг задумался: "И как же их порождать?"

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

Впоследствии оказалось, что придумал я ни что иное, как алгоритм Нарайаны, изобретённый одноимённым индийским математиком. Эх, мне бы поторопиться! Взялся бы я за решение задачи чуть раньше, веков этак на 7, и, глядишь, алгоритм сейчас назывался бы иначе.

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

О перестановках

Сначала разберёмся с тем, что такое перестановка. Перестановкой из n элементов ( n-элементной перестановкой, перестановкой порядка n), где n — натуральное число, будем называть упорядоченный набор, состоящий из n объектов произвольной природы. Сами эти объекты, при этом, будем называть элементами данной перестановки. Набор, не содержащий ни одного объекта, будем назвать пустой, 0-элементной перестановкой или перестановкой нулевого порядка.

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

Перестановки n-го порядка будем записывать в виде пары открывающейся и закрывающейся квадратных скобок, внутри которой через запятую перечисляются элементы перестановки в том порядке, в котором они в ней расположены. Вот пример двух перестановок 4-го порядка: [1, 2, 3, 4], [3, 2, 4, 1]. Пустую перестановку будем обозначать так: [].

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

Любые 2 перестановки n-го порядка состоят из одних и тех же элементов. Если порядок элементов при этом совпадает, то такие перестановки будем называть равными или совпадающими. А если не совпадает, то такие перестановки будем называть неравными, различными или несовпадающими. Можно показать, что количество всех попарно различных перестановок из n элементов равно n!.

Равенство двух n-элементных перестановок a и b будем обозначать так: a = b.

Формулировка задачи

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

Написать программу, генерирующую все n! перестановок из n элементов.

А теперь можно приступать к решению.

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

Зададимся целью научиться генерировать все существующие n-элементные перестановки в определённом порядке. Для того, чтобы задать этот порядок, предложим следующий способ сравнения перестановок.

Рассмотрим 2 несовпадающие перестановки a = [a₁, a₂, …, a_n] и b = [b₁, b₂, …, b_n]. Будем говорить, что перестановка a больше перестановки b или, что то же самое, перестановка b меньше перестановки a, если выполнено одно из следующих двух условий:

Факт заключающийся в том, что перестановка a больше перестановки b, будем обозначать так: a > b или b b или a b и b > с, будет выполнено a > c, то любой набор перестановок n-го порядка можно единственным образом упорядочить так, что за каждая последующая перестановка превышает предыдущую.

А теперь давайте рассмотрим алгоритм получения на основе n-элементной перестановки a = [a₁, a₂, …, a_n] превышающей её перестановки b, при условии, что она существует (т. е. a не является наибольшей перестановкой). Это тот самый алгоритм Нарайаны, упоминавшийся в начале статьи. Вот он:

Шаг 1. Находим наибольший номер i (если он существует), такой, что a_ia_j+1 следует, что a_i >a_j+1, т. к. в противном случае a_j не было бы наименьшим числом среди чисел a_i+1, a_i+2, …, a_n, превосходящим a_i (см. шаг 3). В результате, после применения шага 5, все элементы итоговой перестановки b с номерами, превышающими i, оказываются упорядоченными в порядке возрастания.

Эти 2 утверждения об упорядоченности элементов перестановок a и b, имеющих номера с i + 1-го по n-й, нам ещё пригодятся в дальнейшем.

Как мы видим, перестановка b, полученная в результате выполнения алгоритма, удовлетворяет неравенству b > a, т. к. первые i − 1 элементов перестановок a и b совпадают (при условии, что i > 1), а a_j > a_i, т. е. i-й элемент b больше i-го элемента a.

Таким образом, если мы возьмём в качестве начальной n-элементной перестановки наименьшую, то, многократно генерируя по приведённому рекуррентному алгоритму новые перестановки, в итоге придём к наибольшей перестановке, получив, в итоге, цепочку перестановок n-го порядка. Но можно ли утверждать, что любая n-элементная перестановка будет являться одним из звеньев в полученной цепочке?

Ответ на это вопрос утвердителен. Давайте докажем это от противного. Предположим, что найдётся перестановка c = [c₁, c₂, …, c_n], которая не является звеном в упомянутой выше цепочке. Тогда, поскольку c не совпадает ни с наименьшей n-элементной перестановкой, ни с наибольшей, найдутся две перестановки a и b, являющиеся соседними звеньями в цепочке, такие, что a 1) элементов перестановки c должны совпадать с первыми i − 1 элементами перестановки a (а значит, и с первыми i − 1 элементами перестановки b). Действительно, из [c₁, c₂, …, c_i-1] [a₁, a₂, …, a_i-1] следовало бы, что c > b, но ни того, ни другого быть не может в силу нашего предположения о том, что a a и того, что первые i − 1 элементов (при условии, что i > 1) перестановок a и c совпадают, следует, что c_i > a_i.

Аналогично: из того, что все элементы перестановки b, начиная с i + 1-го, расположены в ней по возрастанию, следует, что среди всех перестановок, первые i элементов которых совпадают с первыми i элементами перестановки b, перестановка b является наименьшей. Отсюда, с учётом того, что с 1) перестановок b и c совпадают, следует, что c_i 1. Но чисел, стоящих в перестановке a правее числа a_i, заключённых между a_i и a_j, не существует, т. к. a_j — это наименьшее из чисел, стоящих в a правее числа a_i, превосходящих a_i (см. 3-й шаг алгоритма). Значит, все числа, заключённые между a_i и a_j, расположены в a левее a_i (т. е. имеют индексы меньшие i). Однако, в силу того, что первые i − 1 элементов перестановки c совпадают с первыми i − 1 элементами перестановки a, все эти числа (заключённые между a_i и a_j) и в перестановке c также имеют индексы меньшие i, т. е. число c_i одним из таких чисел быть никак не может. Значит, и в этом случае числа c_i, удовлетворяющего неравенству a_i

Таким образом, мы пришли к следующему алгоритму генерации всех n-элементных перестановок:

• Шаг 1. Полагаем: a = [1, 2, …, n].
• Шаг 2. Пытаемся с помощью алгоритма Нарайаны сформировать на основе перестановки a перестановку b.
• Шаг 3. В случае успеха полагаем: a = b и переходим к шагу 2.
• Шаг 4. Завершаем работу алгоритма.

А теперь переходим к программированию.

Создание программы

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

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

Программа будет состоять из единственного файла, начинающегося со следующих директив #include :

Заголовочный файл conio.h понадобится нам для использования функции getche () , выполняющей чтение одного символа с консоли. Обратите внимание на то, что ни этот файл, ни данная функция не предусмотрены ни в одном из стандартов языка C, в силу чего компилятор не обязан их поддерживать.

Алгоритм Нарайаны реализуем в функции next () . Вот как она выглядит:

Функция принимает в качестве параметров адрес массива, содержащего перестановку, и количество его элементов. Она пытается сгенерировать новую перестановку на основе данной и записать её в тот же массив. В случае удачи функция возвращает true , а в противном случае — false . Внутри функции массив, как мы видим, называется perm (от англ. permutation — перестановка).

В соответствии с 1-м шагом алгоритма, пытаемся найти i — наибольший индекс элемента массива perm , для которого выполнено неравенство perm[i] > perm[i + 1] (стр. 10-12). Обратите внимание на то, что в случае успеха значение переменной i не совпадёт с числом i из алгоритма, поскольку элементы перестановки нумеруются, начиная с единицы, а элементы массива — начиная с нуля. Так что значение i на единицу меньше i.

Если попытка окажется неудачной, в переменной i окажется значение -1 . В этом случае функция возвратит false и прекратит работу (стр. 13-14).

В случае удачи, в соответствии с шагом 5 алгоритма, меняем порядок элементов массива, имеющих индексы, превышающие i (стр. 15-16).

Далее, согласно шагу 3, находим j — индекс наименьшего из элементов массива, индексы которых не меньше, чем i + 1 , превышающего perm[i] (стр. 17-19). Затем, в соответствии с шагом 4, меняем местами значения элементов perm[i] и perm[j] (стр. 20). Новая перестановка успешно сгенерирована; остаётся лишь вернуть true (стр. 21).

Обратите внимание на две вещи. Во-первых, в строках 16 и 20 два элемента массива обмениваются значениями, т. е. выполняется транспозиция значений. Она реализована в виде макроса trans () , который определён в строках 1-6. Кстати, точки с запятой в строках 16 и 20 необязательны, но без них как-то непривычно.

Во-вторых, в алгоритме Нарайаны порядок двух действий, одно из которых описано в шагах 3, 4, а другое — в шаге 5, неважен. Мы воспользовались этим, и, реализуя алгоритм, изменили порядок этих действий (т. е. сначала реализовали шаг 5, а затем — шаги 3, 4). Причина этого — в том, что, если мы движемся от начала массива к концу, то немного проще искать наименьший элемент массива, не превосходящий заданное значение, если элементы упорядочены по убыванию, а не по возрастанию. Из-за этого полученное значение j оказывается вообще никак не связанным с числом j из алгоритма.

Кстати, упорядоченность элементов массива, среди которых мы проводим поиск в строках 18-19, позволяет использовать бинарный поиск. Но в нашем случае это лишнее, поскольку экономия времени будет минимальной.

В следующей функции реализован второй алгоритм предыдущего раздела.

Функция generate () принимает в качестве параметра неотрицательное целое число и выводит на печать все перестановки, порядок которых равен этому числу.

Сначала обрабатывается случай, когда порядок перестановки, хранящийся в переменной n , нулевой (стр. 3-7). В этом случае на консоль выводится [] , и работа функции завершается.

В противном случае создаём массив perm размера n (стр. 8) и заполняем его числами от 1 до n включительно (стр. 9-10). Теперь в perm хранится наименьшая перестановка. Далее в цикле do while многократно распечатываем текущую перестановку и генерируем посредством вызова функции next () следующую, до тех пор, пока очередной вызов next () не вернёт false (см. стр. 11-18).

Последняя функция нашей программы — это функция main () :

Функция очень простая. В ходе одной итерации бесконечного цикла while () пользователю предлагается ввести число от 0 до 9 или символ 'q' (стр. 5). При вводе 'q' работа программы завершается (стр. 8, 9), а при вводе числа посредством вызова функции generate () на консоль выводятся все перестановки, степень которых равна этому числу (стр. 10, 11), после чего происходит переход к следующей итерации. Если пользователь вводит символ, отличный от 11-ти допустимых, на консоль выводится сообщение об ошибке (стр. 12, 13) и также осуществляется переход к следующей итерации.

Как вы видите, я ввёл ограничение на вводимые числа: они не могут превышать 9, хотя функция generete () "справится" с любым неотрицательным числом, не выходящим за границы диапазона типа int . Для тестирования функций next () и generete () нам вполне хватит чисел от 0 до 9. К тому же, в этом случае пользователю достаточно ввести единственный символ, а значит, нам не требуется реализовывать чтение строк с консоли, и мы можем позволить себе воспользоваться уже упоминавшейся функцией getche () (стр. 6).

Выполнение программы

В результате запуска программы на выполнение может состояться, например, следующий диалог с пользователем:

Как мы видим, программа работает корректно. Задача решена!

Заключение

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

А как генерировать все размещения из n элементов по m? Для этого нужно совместить обе программы. Сначала перебираем все сочетания из n элементов по m. Затем для каждого сочетания строим все перестановки из m элементов, входящих в это сочетание. Все построенные таким образом перестановки в совокупности и будут образовывать все размещения из n элементов по m.

вторник, 8 февраля 2011 г.

Часть 2. Генерация перестановок без повторений. Episode 1

[Все темы по перестановкам]

Теория:
1) Липский. Комбинаторика для программистов. 1988
2) Меньшиков. Олимпиадные задачи по программированию. 2006.

Рассмотрим две задачи:
1) Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
2) Рекурсивный способ генерации всех перестановок в антилексикографическом порядке.

Для начала разберемся, что такое лексико- и антилексико-графические порядки.
Начальная перестановка: <1, 2, 3>

Лексикографический

Антилексикографический

Напомним, что лексикографический порядок – это порядок слов, который используется в словарях.
Слово A меньше слова B, если первые i символов слов равны, а символ A[i+1] Антилексикографический порядок отличается от лексикографического только тем, что сравнение символов идет справа налево.
Слово A меньше слова B, если последние i символов равны, а символ A[i-1] Практика:
Решим задачу 2B-Перестановки из задачника Федора Меньшикова двумя рассматриваемыми способами.
Как можно было заметить, оба порядка начинаются с минимальной перестановки <1, 2, 3>и заканчивается максимальной <3, 2, 1>.

1) Генерация всех перестановок в лексикографическом порядке.

1. int n;
2. vector int > p;
3. vector bool > used;
4. string str;
5. .
6. void lex ( int pos)
7. <
8. if (pos == n) <
9. for ( int i=0;i return ;
10. >
11. for ( int i=0;i if (!used[i]) <
12. used[i] = true ;
13. p[pos] = i;
14. lex (pos+1);
15. p[pos] = 0; // debug only
16. used[i] = false ;
17. >
18. >
19. >

* This source code was highlighted with Source Code Highlighter .

Рекурсивная функция lex (n) генерируется все перестановки из алфавита <0,1. n-1>длиной n и хранит текущую перестановку в массиве p. Если номер текущей позиции pos == n, тогда сгенерирована следующая перестановка.
[Решение]

2) Генерация всех перестановок в антилексикографическом порядке
Решение полностью идентично, за исключением того, что перестановка формируется с конца
[Решение]

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача : Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N!. Действительно:

• на первое место может быть помещен любой из N элементов (всего вариантов N),
• на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1)),
• если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1, то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N, а последней — N N-1 … 1.

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

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

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

Реализация на С++

Результат выполнения

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

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n₁, n₂. n_k, где элемент n₁ повторяется r₁ раз, n₂ повторяется r₂ раз и т.д. При этом n₁+n₂+. +n_k=N. Если мы будем считать все n₁+n₂+. +n_k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n₁+n₂+. +n_k)! . Однако среди этих перестановок не все различны. В самом деле, все r₁ элементов n₁ мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n₂, n₃ и т. д. В итоге имеем r₁! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n₁. Таким образом, всякая перестановка может быть записана r₁!·r₂!·. ·r_k! способами. Следовательно, число различных перестановок с повторениями равно

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

Результат работы приведенного выше алгоритма: