Участник: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. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего.