Реферат: Генерация комбинаторных объектов

Первая из таких перестановок это

1 2 3 4 5 6 7 8 9

Пусть текущая перестановка из 9 компонент:

1 9 5 8 4 7 6 3 2

Каким будет следующее значение перестановки, если мы строим ее в лексикографическом порядке (то есть в порядке возрастания величины числа, составленного из этих цифр)?

Правильный ответ таков :

1 9 5 8 6 2 3 4 7

Как он получается?

Прежде всего, необходимо просматривать исходный массив от конца к началу, что бы найти первое число, которое МЕНЬШЕ предыдущего в нашем случае - это 4

(7>6>3>2, а 4<7)

Далее среди просмотренных чисел справа от найденной 4 мы ищем последнее число которое больше 4. Это число 6.

(7>4, 6>4, 3<4, 2<4)

Затем меняем эти 2 найденных числа (4 и 6) местами, получаем:

1 9 5 8 6 7 4 3 2

И теперь числа (справа от 6), которые составляют убывающую последовательность (7 4 3 2) , попарно меняем местами так, что бы они составили возрастающую последовательность (2 3 4 7) :

1 9 5 8 6 2 3 4 7

Это и есть следующая перестановка.

А какая перестановка будет последней для данного примера?

Надеюсь, что вдумчивый читатель догадался и сам:

9 8 7 6 5 4 3 2 1

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

1. От конца к началу перестановки ищем первый элемент B[i] такой, что B[i]<B[i+1] запоминаем его индекс - I

2. От элемента I+1 до конца ищем последний элемент, больший чем B[i], запоминаем его индекс - K

3. Меняем местами эти элементы - с номерами I и K

4. Всю группу элементов от i+1-го элемента до N-го попарно меняем местами (i+1-ый элемент с N-ым, i+2-ой элемент с N-1-ым и т.д.)

Формализовано алгоритм генерации всех перестановок из N элементов может быть записан следующим образом:

Ввод N

Прописываем массив B последовательно числами от 1 до N

Это первая - начальная - перестановка, выводим ее