Генерация перестановок из n элементов
Постановка задачи
Дано число n, n > 1. Получить все перестановки элементов множества {1, 2, ..., n}.
Перестановка— это упорядоченный набор чисел 1, 2, ..., n , которая числу i ставит соответствие i-й элемент из набора. Число n при этом называется порядком перестановки.
Перестановка - это упорядоченный набор элементов. Это означает, что порядок элементов в наборе имеет значение. И две перестановки, состоящие из одних элементов, расположенных в разном порядке различными.
Методы решения и описание алгоритмов
Количество различных перестановок множества, состоящего из n элементов равно n!. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из n элементов множества, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из n – 1 оставшегося элемента и т.д. Таким образом, общее количество вариантов равно n(n – 1)(n – 2)...3*2*1 = n!
итеративный рекурсивный программный граф
Генерация всех перестановок по индексам
Алгоритм заключается в поиске n-факториального представления числа i и восстановлению перестановки по найденному представлению. Мы не будем рассматривать его подробно, так как время работы данного алгоритма есть O(nn!), что не является оптимальным, как в случае следующих алгоритмов.
Циклический сдвиг
Циклический сдвиг заключается в последовательном сдвиге по циклу на один разряд всех n элементов. При завершении круга, т.е. возвращении к исходной перестановке, осуществляется сдвиг первых n-1 элементов, далее, если и этот шаг возвращает нас к уже полученной перестановке, сдвигаем на один разряд первые элементов и т.д.
Алгоритм генерации перестановок в антилексикографическом порядке
Алгоритм для генерации перестановок в антилексикографическом порядке может базироваться на двух утверждениях:
Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно (1, 2, …, n) и (n, n-1,…,1).
Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.
Алгоритм генерации перестановок в лексикографическом порядке:
При генерации перестановок в лексикографическом порядке, начиная с тождественной перестановки (1,2,..,n), требуется переходить от уже построенное перестановки a=(a1,…an) к непосредственно следующей за ней перестановкой b=(b1,..bn) до тех пор, пока не получим наибольшую перестановку (n,n-1…,1)(относительно лексикографического порядка).
Рассмотрим способ построения такой перестановки b.Просматриваем справа налево перестановку a=(a1,…an) в поисках самой правой позиции i такой, что aii+1.Если такой позиции нет, то a1>a2>...>an,т.е. a=(n,n-1,…,1) и генерировать больше нечего. Поэтому считаем, что такая позиция i есть. Значит , aii+1>ai+2>…>an. Далее ищем первую позицию j при переходе от позиции n к позиции i такую, что aij. Тогда ii и aj, а в полученной перестановке a,=(a`1,…,a`n)отрезок a`1,…,a`n-1, a`n переворачиваем. Построенную перестановку обозначим через b. Например, пусть a=(2,6,5,8,7,4,3,1). Тогда ai=5 и aj=7. Поменяем местами эти элементы, повернем отрезок (8,5,4,3,1) и получим перестановку b=(2,6,7,1,3,4,5,8).
Сложность такого алгоритма - O(n!).
Программа, демонстрирующая генерации перестановок в лексикографическом порядке представлена в приложении.
Do'stlaringiz bilan baham: |