Участник:ZeRoGerc — различия между версиями
ZeRoGerc (обсуждение | вклад) (→Идея) |
ZeRoGerc (обсуждение | вклад) (→Идея) |
||
| Строка 3: | Строка 3: | ||
== Идея == | == Идея == | ||
Сопоставим каждому элементу перестановки <tex>p[i]</tex> направление <tex>d[i]</tex>. Будем указывать направление при помощи стрелок '''←''' ("влево") или '''→'''("вправо"). Назовём элемент подвижным, если по направлению стелки стоит элемент меньше его. Например для <tex>p</tex> = ''{1, 3, 2, 4, 5}'' и <tex>d</tex> = ''{←, →, ←, →, ←}'', подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. | Сопоставим каждому элементу перестановки <tex>p[i]</tex> направление <tex>d[i]</tex>. Будем указывать направление при помощи стрелок '''←''' ("влево") или '''→'''("вправо"). Назовём элемент подвижным, если по направлению стелки стоит элемент меньше его. Например для <tex>p</tex> = ''{1, 3, 2, 4, 5}'' и <tex>d</tex> = ''{←, →, ←, →, ←}'', подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего. | ||
| + | == Пример работы алгоритма == | ||
Версия 22:12, 27 ноября 2014
Алгоритм Джонсона-Троттера(англ. Johnson-Trotter algorithm) - алгоритм генерации всех перестановок из элементов. Причём любая перестановка отличаются от предыдущей транспозицией двух соседних элементов.
Идея
Сопоставим каждому элементу перестановки направление . Будем указывать направление при помощи стрелок ← ("влево") или →("вправо"). Назовём элемент подвижным, если по направлению стелки стоит элемент меньше его. Например для = {1, 3, 2, 4, 5} и = {←, →, ←, →, ←}, подвижными являются элементы 3 и 5. На каждой итерации алгоритма будем искать наибольший подвижный элемент и менять местами с элементом, который стоит по направлению стрелки. После чего поменяем направление стрелок на противоположное у всех элементов больших текущего.
