Меню

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



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

Перестановка – это комбинация элементов из 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 элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n1, n2. nk, где элемент n1 повторяется r1 раз, n2 повторяется r2 раз и т.д. При этом n1+n2+. +nk=N. Если мы будем считать все n1+n2+. +nk элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n1+n2+. +nk)! . Однако среди этих перестановок не все различны. В самом деле, все r1 элементов n1 мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n2, n3 и т. д. В итоге имеем r1! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n1. Таким образом, всякая перестановка может быть записана r1!·r2!·. ·rk! способами. Следовательно, число различных перестановок с повторениями равно

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

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

Источник

Элементы комбинаторики. Перестановки, размещения, сочетания

Подсчет числа перестановок, размещений и сочетаний.

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

Элементы комбинаторики. Перестановки, размещения, сочетания

Итак, есть множество из n элементов.

Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов — А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:

Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА

Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m

Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ

Также бывают размещения с повторениями, как ясно из названия, элементы на определенных позициях могут повторяться.
Число всех размещений из n по m с повторениями:

Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC

Читайте также:  Немецкий электротехник промышленник создавший генератор с самовозбуждением

Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m

Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ

Приведем до кучи формулу соотношения между перестановками, размещениями и сочетаниями:

Источник

Зона кода

Листал я недавно книгу Никлауса Вирта «Алгоритмы и структуры данных» 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 = [a1, a2, …, an] и b = [b1, b2, …, bn]. Будем говорить, что перестановка a больше перестановки b или, что то же самое, перестановка b меньше перестановки a, если выполнено одно из следующих двух условий:

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

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

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

Читайте также:  Генератор случайных чисел правда ли это

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

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

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

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

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

Таким образом, мы пришли к следующему алгоритму генерации всех 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.

Источник