В первой перестановке элементы идут в растущей последовательности, а в последней – в убывающей; другими словами последняя перестановка является обращением первой

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

В качестве примера рассмотрим генерирование всех перестановок для п =4. Таких перестановок будет 4!=24. Эти перестановки можно разбить на четыре блока, каждый из которых содержит 3!=6 перестановок, по значению элемента в первой позиции. В первом блоке на первом месте стоит 1, во втором – 2, в третьем – 3, в четвертом – 4. Далее рассмотрим блок с 1 на первом месте, для остальных аналогично. Для генерации всех перестановок оставшегося множества Х ={2,3,4} выполним следующее: разобъем все перестановки на 3 блока по 2!=2 перестановки, соответствующих возрастающим значениям элемента в первой позиции, в первом блоке – 2, во втором – 3, в третьем – 4. Далее в каждом блоке генерируем все перестановки из оставшихся двух элементов в лексикографическом порядке (в первой из перестановок последние два элемента расположены в порядке возрастания). В результате получаем:

Генерирование всех перестановок заданного множества в антилексикографическом порядке

Антилексикографический порядок (обозначим <¢) определяется следующим образом:

<x1,x2,…xn> <¢ <y1,y2,…,y n> Û существует такое k£n, что xk > yk и xp = yp для каждого p > k..

Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.

Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:

1) в первой перестановке элементы идут в растущей последовательности, в последней – в убывающей; другими словами, последняя перестановка – обращение первой,

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

Сгенерируем в антилексикографическом порядке все перестановки для n=4, получим

ЗАДАНИЕ 6. Построить гамильтонов цикл в графе, используя нерекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке

ЗАДАНИЕ 7. Построить гамильтонов цикл в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке

ЗАДАНИЕ 8. Построить гамильтонов цикл в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке.

ЗАДАНИЕ 9. Построить гамильтонову цепь в графе, используя нерекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке

ЗАДАНИЕ 10. Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке

ЗАДАНИЕ 11. Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке.

ЗАДАНИЕ 12. Построить гамильтонов цикл в графе, используя алгоритм с возвратом.

ЗАДАНИЕ 13. Построить гамильтонову цепь в графе, используя алгоритм с возвратом.