Просмотр кода страницы Алгоритм Джонсона — Троттера

[[Файл:Symmetric group 4; Cayley graph 1,2,6 (3D); Steinhaus–Johnson–Trotter.svg|thumb|360px|[[Гамильтонов граф#Связанные термины|Гамильтонов цикл]] в [[Граф Кэли|графе Кэли]] симметрической группы, образованный алгоритмом Джонсона — Троттера]]
[[Файл:Symmetric group 4; permutation list; Steinhaus–Johnson–Trotter.svg|thumb|360px|Перестановки четырёх элементов, их множества [[Инверсия (перестановка)|инверсий]] (множества пар элементов, нарушающие натуральный порядок), вектора инверсий и числа инверсий.<br>Множества инверсий образуют код Грея.<br>Числа слева — обратные [[Лексикографический порядок|колексикографиеческие]] индексы (сравните с [[commons:File:Symmetric group 4; permutation list.svg|списком в естественном порядке]]), они образуют строку в треугольнике {{OEIS2C|A280319}}.<br>Строки на расстоянии 12 друг от друга являются дополнительными.]]
[[Файл:Wheel diagram of Steinhaus-Johnson-Trotter algorithm for n=4.svg|thumb|Круговая диаграмма перестановок длины <math>n=4</math>, созданных алгоритмом Джонсона — Троттера, где каждая перестановка закодирована цветом (1=синий, 2=зелёный, 3=жёлтый, 4=красный).]]
'''Алгоритм Джонсона — Троттера''' (''Штейнгауса — Джонсона — Троттера'') — [[алгоритм]], генерирующий все [[Перестановка|перестановки]] <math>n</math> элементов, на каждом шаге проводящий обмен местами двух соседних элементов. Эквивалентно — алгоритм находит [[Гамильтонов граф#Связанные термины|гамильтонов цикл]] в [[Перестановочный многогранник|перестановочном многограннике]].

Назван по именам [[Джонсон, Селмер|Селмера Джонсона]] и [[Троттер, Хейл|Хейла Троттера]], описавших алгоритм в 1962—1963 годах, однако фактически метод тривиален и известен издавна, например, с XVII века используется в распространённом в англиканской церкви колокольном перезвоне под названием {{нп5|change ringing}}{{sfn|Sedgewick|1977}}. Алгоритм можно реализовать таким образом, что время на создание каждой отдельной перестановки будет постоянным. Будучи простым и одновременно вычислительно эффективным, этот алгоритм имеет преимущество, что вычисления на перестановках, которые образует алгоритм, можно ускорить ввиду похожести соседних перестановок{{sfn|Sedgewick|1977}}.

== Алгоритм ==
Последовательность перестановок, образованных алгоритмом Джонсона — Троттера, имеет естественную [[Рекурсивная функция|рекурсивную]] структуру, которая может быть образована рекурсивным алгоритмом. Однако реальный алгоритм Джонсона — Троттера не использует рекурсии и вместо неё вычисляет ту же последовательность перестановок с помощью простого итеративного метода. Дальнейшее улучшение алгоритма позволяет получать каждую перестановку за постоянное время.

=== Рекурсивная структура ===
Последовательность перестановок для заданного числа <math>n</math> может быть образована из последовательности перестановок для <math>n-1</math> путём размещения числа <math>n</math> во все возможные позиции каждой из более коротких перестановок. Алгоритм Джонсона — Троттера следует следующей структуре: последовательность перестановок, которые он образует, состоит из <math>(n-1)!</math> блоков перестановок, так что внутри каждого блока перестановок сохраняется порядок чисел от 1 до <math>n-1</math> и перестановки отличаются только положением числа <math>n</math>. Сами блоки упорядочены рекурсивно согласно алгоритму Джонсона — Троттера для набора без одного элемента.
Внутри каждого блока положения, в котором находится число <math>n</math>, идут в убывающем или возрастающем порядке, меняя порядок с каждым следующим блоком. Позиции числа <math>n</math> в первом блоке идут в убывающем порядке, во втором блоке в возрастающем порядке, в третьем блоке в убывающем и так далее{{sfn|Lenstra, Kan|1979}}{{sfn|Savage|1997|с=section 3}}.

Тогда для единственной перестановки одного элемента,
: 1
можно поместить число 2 в каждую возможную позицию в убывающем порядке, что образует список из двух перестановок двух элементов,
: 1 '''2'''
: '''2''' 1
Теперь можно поместить число 3 в каждую из трёх различных позиций для этих двух перестановок, начиная с убывающего порядка для первой перестановки 1 2, а затем в возрастающем порядке для перестановки 2 1:
: 1 2 '''3'''
: 1 '''3''' 2
: '''3''' 1 2
: '''3''' 2 1
: 2 '''3''' 1
: 2 1 '''3'''
Продолжаем ту же процедуру для последующих значений <math>n</math>, меняя убывающий и возрастающий порядок с каждой перестановкой.
В последовательности перестановок в этой рекурсивной структуре каждая перестановка отличается от предыдущей позицией <math>n</math> или меняются два меньших числа, унаследованных от предыдущей последовательности более коротких перестановок. В любом случае перестановки отличаются лишь обменом местами двух соседних элементов. Если <math>n > 1</math>, первая и последняя перестановки в последовательности отличаются лишь двумя соседними элементами (в позициях <math>1</math> и <math>2</math>), что можно доказать по индукции.

Эту последовательность можно получить с помощью [[Рекурсивная функция|рекурсивного алгоритма]], который создаёт последовательность перестановок меньшего размера, а затем осуществляет все возможные вставки наибольшего числа в созданную рекурсивно последовательность{{sfn|Lenstra, Kan|1979}}{{sfn|Savage|1997|с=section 3}}. Тот же самый порядок перестановок может быть описан как порядок, образованный следующим жадным алгоритмом{{sfn|Williams|2013}}.
Начинаем с тождественной перестановки <math>1\;2\;\ldots\;n</math>.
Теперь последовательно переставляем наибольший элемент с левым или правым элементом так, что на каждом шаге образуется новая перестановка, которая не встречалась в списке перестановок до этого. Например, в случае <math>n=3</math> последовательность начинается с <math>1\;2\;3</math>, затем переставляется <math>3</math> с левым соседом что приводит к <math>1\;3\;2</math>.
В этом месте перестановка <math>3</math> с правым соседом <math>2</math> приведёт к начальной перестановке <math>1\;2\;3</math>, так что снова переставим <math>3</math> с левым соседом <math>1</math> и получаем <math>3\;1\;2</math>, и так далее. Направление обмена позиций (слева или справа) в алгоритме всегда определяется однозначно.
Однако действительный алгоритм Джонсона — Троттера не использует рекурсию и не требует хранения списка созданных перестановок. Вместо этого алгоритм вычисляет ту же последовательность перестановок простым [[Итеративный метод|итеративным методом]].

=== Исходная версия ===
Согласно варианту Джонсона{{sfn|Johnson|1963}}, алгоритм создания следующей перестановки из заданной перестановки <math>\pi</math> осуществляется посредством следующих шагов:
* для любого <math>i</math> от 1 до <math>n</math> пусть <math>x_i</math> будет позицией, в которой значение <math>i</math> помещается в перестановке <math>\pi</math>, если порядок чисел от 1 до <math>i-1</math> в перестановке <math>\pi</math> определяет [[Перестановка|чётную перестановку]], пусть <math>y_i=x_i-1</math>, в противном случает пусть <math>y_i=x_i+1</math>;
* находится наибольшее число <math>i</math>, для которого <math>y_i</math> определяет верное положение в перестановке <math>\pi</math>, которая содержит число, меньшее <math>i</math>; меняются местами значения в позициях <math>x_i</math> и <math>y_i</math>.
Если нет числа <math>i</math>, удовлетворяющего условиям второго шага алгоритма, алгоритм достиг финальной перестановки и прекращает работы.
Эту процедуру можно реализовать со временем <math>O(n)</math> на перестановку.

Троттер{{sfn|Trotter|1962}} дал альтернативную реализацию итеративного алгоритма для той же последовательности с комментариями в стиле [[Алгол-60|Алгола-60]].

Поскольку метод создаёт перестановки с чередованием чётных и нечётных, его легко модифицировать для создания только чётных перестановок или только нечётных перестановок — чтобы образовать следующую перестановку той же чётности просто выполняется та же процедура дважды{{sfn|Knuth|2011}}.

=== Ускорение алгоритма Ивеном ===
Улучшение алгоритма Шимоном Ивеном даёт улучшение времени выполнения путём запоминания дополнительной информации для каждого элемента в перестановке — его позицию и ''направление'' (положительное, отрицательное или нулевое), в котором элемент движется (по существу, это та же информация, которая вычисляется с помощью чётности перестановки в версии алгоритма Джонсона). Начально направление числа 1 равно нулю, а все остальные элементы имеют отрицательные направления:
: 1 −2 −3
На каждом шаге алгоритм находит наибольший элемент с ненулевым направлением и переставляет его в указанном направлении:
: 1 −3 −2
Если это приводит к тому, что выбранный элемент оказывается в первой или последней позиции внутри перестановки, или если следующий элемент в том же направлении больше выбранного элемента, направление выбранного элемента сбрасывается в ноль:
: 3 1 −2
После каждого шага все элементы, большие выбранного элемента (имевшего нулевое направление), имеют направления, указывающие направление движения к выбранному элементу. То есть, направление положительно для элементов между началом перестановки и выбранным элементом и отрицательно для элементов от выбранного элемента до конца. Таким образом, в данном примере, после сдвига числа 2, число 3 помечается положительным направлением:
: +3 2 1
Оставшиеся два шага алгоритма для <math>n=3</math>:
: 2 +3 1
: 2 1 3
Когда все числа остаются без пометок, алгоритм завершает работу.

Этот алгоритм работает за время <math>O(i)</math> на каждом шаге, в котором наибольшее число для обмена равно <math>n-i+1</math>. Таким образом, обмен позиций, вовлекающих число <math>n</math>, занимает постоянное время. Поскольку каждый такой обмен имеет место лишь для <math>1/n</math> части от всех операций обмена, выполняемых алгоритмом, среднее время на перестановку постоянно, даже если некоторое небольшое количество перестановок занимает бо́льшее время{{sfn|Sedgewick|1977}}.

Более сложная версия алгоритма {{нп5|Алгоритм без циклов|без циклов||Loopless algorithm}} той же самой процедуры позволяет выполнять её за постоянное время на перестановку, но в этой модификации нужно исключить циклы из процедуры, что делает процедуру на практике медленнее{{sfn|Ehrlich|1973}}{{sfn|Dershowitz|1975}}{{sfn|Sedgewick|1977}}.

== Связанные структуры ==

=== Перестановочный многогранник ===
Множество всех перестановок <math>n</math> элементов можно представить геометрически как [[перестановочный многогранник]], то есть [[многогранник]], образованный из [[Выпуклая оболочка|выпуклой оболочки]] <math>n!</math> векторов, представляющих перестановки вектора <math>(1,2,\dots n)</math>. Хотя многогранник таким образом определяется в <math>n</math>-мерном пространстве, на самом деле он является <math>(n-1)</math>-мерным многогранником. Например, перестановочный многогранник четырёх элементов является трёхмерным многогранником, а именно, [[Усечённый октаэдр|усечённым октаэдром]]. Если пометить каждую вершину перестановочного многогранника [[Обратный элемент|обратной перестановкой]] к перестановке, определённой координатами вершины, получающаяся разметка описывает [[граф Кэли]] [[Симметрическая группа|симметрической группы]] перестановок <math>n</math> элементов, поскольку образуется перестановками, в которых переставляются соседние пары элементов. Тогда любые две последовательные перестановки, образованные алгоритмом Джонсона — Троттера соответствуют в этом пути двум конечным вершинам ребра в перестановочном многограннике, а вся последовательность перестановок описывает [[Гамильтонов граф#Связанные термины|гамильтонов путь]] в перестановочном многограннике, путь, проходящий через все вершины ровно один раз. Если последовательность перестановок дополнить ещё одним ребром, соединяющим последнюю перестановку с первой, в результате получим гамильтонов цикл{{sfn|Savage|1997|с=section 11}}.

=== Коды Грея ===
[[Код Грея]] для чисел с заданным [[Основание системы счисления|основанием]] — это последовательность, которая содержит каждое число до указанного предела ровно один раз, и в этой последовательности каждая пара последовательных чисел отличаются одной цифрой. <math>n!</math> перестановок <math>n</math> чисел от 1 до <math>n</math> могут быть расположены в соответствии один-к-одному с <math>n!</math> числами от 0 до <math>n!-1</math> путём связывания каждой перестановки с последовательностью чисел <math>c_i</math>, которые соответствуют числу позиций в перестановке, находящихся справа от значения <math>i</math> и содержащих значение, меньшее <math>i</math> (то есть, число [[Инверсия (перестановка)|инверсий]] для каждого <math>i</math>), затем эти последовательности как числа в [[Факториальная система счисления|факториальной системе счисления]], то есть в {{нп5|Смешанное основание системы счисления|смешанной системе счисления||mixed radix}} с последовательностью оснований <math>(1,2,3,4,\dots)</math>. Например, перестановка <math>(3,1,4,5,2)</math> даст значения <math>c_1=0</math>, <math>c_2=0</math>, <math>c_3=2</math>, <math>c_4=1</math> и <math>c_5=1</math>. Последовательность этих значений <math>(0,0,2,1,1)</math> задаёт число:
: <math>0\times 0!+0\times 1!+2\times 2!+1\times 3!+1\times 4!=34</math>.
Последовательные перестановки в последовательности, генерируемой алгоритмом Джонсона — Троттера имеют числа инверсий, что отличаются на единицу, образуя код Грея для факториальной системы{{sfn|Dijkstra|1976}}{{sfn|Knuth|2011}}.

Исследователи комбинаторных алгоритмов определяют код Грея для набора комбинаторных объектов как упорядочение объектов, в котором каждые два последовательных объекта отличаются минимально возможным образом. В этом обобщённом смысле алгоритм Джонсона — Троттера образует код Грея для самих перестановок.

== См. также ==
* {{нп5|Алгоритм Хипа|||Heap's algorithm}} — другой метод перечисления всех перестановок
* [[Тасование Фишера — Йетса]] — метод создания случайных перестановок

== Примечания ==
{{примечания}}

== Литература ==
* {{статья
|ref= Dershowitz
|автор=Nachum Dershowitz
|выпуск= 2
|издание= Nordisk Tidskr. Informationsbehandling (BIT)
|mr= 0502206
|страницы=158–164
|заглавие= A simplified loop-free algorithm for generating permutations
|том= 15
|год=1975
|doi=10.1007/bf01932689
|s2cid= 121353303
}}
* {{статья
|ref= Dijkstra
|автор= [[Дейкстра, Эдсгер Вибе|Edsger W. Dijkstra]]
|doi= 10.1007/BF00268136
|выпуск=4
|издание= Acta Informatica
|mr= 0426492
|страницы=357–359
|заглавие=On a gauntlet thrown by David Gries
|ссылка= http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD553.PDF
|том= 6
|год=1976
|s2cid = 7085805
}}
* {{статья
|ref=Ehrlich
|автор= Gideon Ehrlich
|doi= 10.1145/321765.321781
|выпуск=3
|издание= Journal of the ACM
|страницы=500–513
|заглавие=Loopless algorithms for generating permutations, combinations, and other combinatorial configurations
|том= 20
|год=1973
|s2cid= 21493963
}}
* {{книга
|ref=Even
|автор= Shimon Even
|издательство=Macmillan
|заглавие=Algorithmic Combinatorics
|ссылка=https://archive.org/details/algorithmiccombi0000even
|год=1973
}}
* {{статья
|ref=Johnson
|автор= Selmer M. Johnson
|doi= 10.1090/S0025-5718-1963-0159764-2
|издание=Mathematics of Computation
|jstor= 2003846
|mr= 0159764
|страницы=282–285
|заглавие=Generation of permutations by adjacent transposition
|ссылка=https://archive.org/details/sim_mathematics-of-computation_1963-07_17_83/page/282
|том= 17
|год=1963
|выпуск=83 
|doi-access= free
}}
* {{Книга|ref=Lenstra, Kan|ссылка=https://ageconsearch.umn.edu/record/272202/files/erasmus129.pdf|автор=Jan Karel Lenstra, Alexander Rinnooy Kan|заглавие=Proceedings of the School on Analysis and Design of Algorithms in Combinatorial Optimization, Udine, Italy. Technical report 8003/0, Erasmus University Rotterdam|год=1979|часть=A recursive approach to the implementation of enumerative methods|язык=en}}; см. Section 2.1, «A minimum-change generator», pp. 3-8
* {{книга
|ref=Knuth 
|автор=[[Кнут, Дональд Эрвин|Donald Knuth]]
|часть=Section 7.2.1.2: Generating All Permutations
|заглавие=The Art of Computer Programming, volume 4A: Combinatorial Algorithms, Part 1
|год=2011
}}
** {{книга:Кнут|4}}
* {{книга
|ref=McGuire 
|автор= Gary McGuire
|заглавие=Bells, motels and permutation groups
|citeseerx= 10.1.1.6.5544
|год=2003
}}
* {{статья
|ref=Savage
|автор=Carla Savage
|doi= 10.1137/S0036144595295272
|выпуск=4
|издание= [[SIAM Review]]
|jstor= 2132693
|mr= 1491049
|страницы=605–629
|заглавие=A survey of combinatorial Gray codes
|том= 39
|год= 1997
|bibcode = 1997SIAMR..39..605S
|citeseerx= 10.1.1.39.1924
}}
* {{статья
|ref=Sedgewick
|автор= Robert Sedgewick
|doi= 10.1145/356689.356692
|выпуск=2
|издание= ACM Comput. Surv.
|страницы=137–164
|заглавие=Permutation generation methods
|ссылка=https://archive.org/details/sim_acm-computing-surveys_1977-06_9_2/page/137
|том= 9
|год=1977
|s2cid= 12139332
}}
<!-- имя Штейнгауза связывают с этой задачей скорее по ошибке, см. англовики
* {{книга
|ref=Steinhaus
|автор= [[Штейнгауз, Гуго|Hugo Steinhaus]]
|место= New York
|mr= 0157881
|страницы=49–50
|издательство=Basic Books
|заглавие=One hundred problems in elementary mathematics
|год=1964
}}
** {{
|автор= Штейнгауз Г.
|заглавие=Сто задач
|издательство= «Наука» Главная редакция физико-математической литературы
|место=Москва
|год=1976
}} -->
* {{статья
|ref=Trotter
|автор= Trotter H. F.
|год = 1962
|месяц = August 
|doi= 10.1145/368637.368660
|выпуск=8
|издание= Communications of the ACM
|страницы=434–435
|заглавие=Algorithm 115: Perm
|том= 5
|s2cid= 1013826
}}
* {{книга
| автор = Williams, Aaron
|ответственный=Frank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack
|часть= The Greedy Gray Code Algorithm
|doi= 10.1007/978-3-642-40104-6_46
|страницы= 525–536
|издательство= Springer
|серия= Lecture Notes in Computer Science
|заглавие=Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings
|том= 8037
|год= 2013
|ref=Williams
}}

{{ВС}}
[[Категория:Комбинаторные алгоритмы]]
[[Категория:Перестановки]]