Участник:ZeRoGerc

Алгоритм Джонсона-Троттера(англ. Johnson-Trotter algorithm) - алгоритм генерации всех перестановок из [math]n[/math] элементов. Причём любая перестановка отличаются от предыдущей транспозицией двух соседних элементов.

Идея

Сопоставим каждому элементу перестановки [math]p[i][/math] направление [math]d[i][/math]. Будем указывать направление при помощи стрелок ← ("влево") или →("вправо"). Назовём элемент подвижным, если по направлению стелки стоит элемент меньше его. Например для [math] p = \{1, 3, 2, 4, 5\},\;d = \{[/math]←, →, ←, →, ←[math]\}[/math], подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. Изначально [math] p = \{1, ... ,n\},\;d = \{[/math]←, ... ,←[math]\}[/math]

Пример работы алгоритма для n = 3

• [math] p = \{1, 2, \textbf{3}\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
• [math] p = \{1, \textbf{3}, 2\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
• [math] p = \{3, 1, \textbf{2}\}\;\;\;d = \{[/math]←, ←, ←[math]\}[/math]
• [math] p = \{\textbf{3}, 2, 1\}\;\;\;d = \{[/math]→, ←, ←[math]\}[/math]
• [math] p = \{2, \textbf{3}, 1\}\;\;\;d = \{[/math]←, →, ←[math]\}[/math]
• [math] p = \{2, 1, 3\}\;\;\;d = \{[/math]←, ←, →[math]\}[/math]