Рекурсия

Рис. 13.7. Генерирование перестановок в лексикографическом порядке

E. Перестановки c одной транспозицией соседних элементов. В этом пункте рассматрива

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

Рекурсивная программа-функция permut5(n) реализует этот, схематично описанный, алгоритм. На рис. 13.8 приведены полученные по permut5(n) перестановки для n=3 и n=4.

Рис. 13.8. Генерирование перестановок c транспозицией соседних элементов

В заключение автор выражает признательность профессорам. Ваграменко Я.А. и Добровольскому Н.М. за консультации и советы при написании пособия.

Литература

1. Кнут Д. Искусство программирования для ЭBM. Основные алгоритмы: т. 1, M.: Мир, 1976.

2. Кнут Д. Искусство программирования для ЭBM. Получисленные алгоритмы: т. 2, М.: Мир, 1977.

3. Кнут Д. Искусство программирования для ЭBM. Сортировка и поиск: т. 3, М.: Мир, 1978.

4. Лекции лауреатов премии Тьюринга. М.: Мир, 1985.

5. Бауэр Ф.Л., Гнац Р., Хилл У. Информатика. Задачи и решения. М.: Мир, 1978 г.

6. Бауэр Ф.Л., Гооз Г. Информатика. T. 1, М.: Мир, 1990 г.

7. Бауэр Ф.Л., Гооз Г. Информатика. T. 2, М.: Мир, 1990 г.

8. Ландау Э. Основы анализа. М.: изд. Иностранной литературы, 1947.

9. http://www-cs-staff.stanford.edu/~knuth/taocp.html#vol4-{volume4}).

 Скачать реферат