Курсовой проект «Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»

Генерация перестановок из 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 элементов, далее, если и этот шаг возвращает нас к уже полученной перестановке, сдвигаем на один разряд первые элементов и т.д.
Алгоритм генерации перестановок в антилексикографическом порядке
Алгоритм для генерации перестановок в антилексикографическом порядке может базироваться на двух утверждениях:

1. 
   Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно (1, 2, …, n) и (n, n-1,…,1).
   
2. 
   Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.
   

Алгоритм генерации перестановок в лексикографическом порядке:
При генерации перестановок в лексикографическом порядке, начиная с тождественной перестановки (1,2,..,n), требуется переходить от уже построенное перестановки a=(a₁,…a_n) к непосредственно следующей за ней перестановкой b=(b₁,..b_n) до тех пор, пока не получим наибольшую перестановку (n,n-1…,1)(относительно лексикографического порядка).
Рассмотрим способ построения такой перестановки b.Просматриваем справа налево перестановку a=(a₁,…a_n) в поисках самой правой позиции i такой, что a_ii₊₁.Если такой позиции нет, то a₁>a₂>...>a_n,т.е. a=(n,n-1,…,1) и генерировать больше нечего. Поэтому считаем, что такая позиция i есть. Значит , a_ii₊₁>a_i+2>…>a_n. Далее ищем первую позицию j при переходе от позиции n к позиции i такую, что a_ij_. Тогда ii и a_j, а в полученной перестановке a,=(a`<sub>1</sub>,…,a`_n)отрезок a`<sub>1</sub>,…,a`_n-1, a`_n переворачиваем. Построенную перестановку обозначим через b. Например, пусть a=(2,6,5,8,7,4,3,1). Тогда a_i=5 и a_j=7. Поменяем местами эти элементы, повернем отрезок (8,5,4,3,1) и получим перестановку b=(2,6,7,1,3,4,5,8).
Сложность такого алгоритма - O(n!).
Программа, демонстрирующая генерации перестановок в лексикографическом порядке представлена в приложении.