Участник:ZeRoGerc

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

Идея

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

Пример работы алгоритма

[math]n = 3[/math]

• [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]