Перестановки с одной транспозицией соседних элементов
Back Home Up

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

Решение. Проиллюстрируем на примере идею соответствующего алгоритма, приписываемого С. Джонсону [6, с. 282-285] и Г. Троттеру [8, с. 433-435]. Предположим, что для элементов {1,2,…, n-1} уже построена требуемая последовательность перестановок U. Тогда из элементов {1,2,…, n} необходимая последовательность может быть построена перемещениями элемента n между начальной и конечной позициями каждой перестановки U. При этом перемещения должны производиться попеременно вперед и назад (n-1)! раз так, как это показано на рис. 5.

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

              (10)

 

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

Отметим, что “генерирование последовательности перестановок, каждая из которых, кроме начальной, отличается от предыдущей перестановки одной транспозицией соседних элементов” и “генерирование последовательности перестановок путем транспозиции двух соседних элементов”- это, разумеется, не одно и то же. Предложенный выше алгоритм соответствует первому из этих высказываний. Однако стоит отметить, что каждые n перестановок, формируемых из конкретной рекурсивно полученной перестановки из n-1 элемента, генерируются в соответствии именно со вторым высказыванием.

Home Содержание Схемы ООД Доска объявлений Поиск