Изменения

Перейти к: навигация, поиск

Коды Грея для перестановок

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

Навигация