Алгоритм Штейнхауса – Джонсона – Троттера

Гамильтонов цикл в графе Кэли симметрической группы, сгенерированный алгоритмом Штейнхауза–Джонсона–Троттера

Колесная диаграмма всех перестановок длины, сгенерированная алгоритмом Штейнхауза-Джонсона-Троттера, где каждая перестановка имеет цветовую кодировку (1=синий, 2=зеленый, 3=желтый, 4=красный). ${\displaystyle n=4}$

Алгоритм Штейнхауза–Джонсона–Троттера или алгоритм Джонсона–Троттера , также называемый простыми изменениями , — это алгоритм, названный в честь Хьюго Штейнхауза , Сельмера М. Джонсона и Хейла Ф. Троттера , который генерирует все перестановки элементов . Каждые две смежные перестановки в результирующей последовательности отличаются обменом двух смежных переставленных элементов. Эквивалентно, этот алгоритм находит гамильтонов цикл в пермутоэдре , многограннике , вершины которого представляют перестановки, а ребра — обмены. ${\displaystyle n}$

Этот метод был известен уже английским звонарям XVII века , и Роберт Седжвик называет его «возможно, самым выдающимся алгоритмом перечисления перестановок». ^[1] Версия алгоритма может быть реализована таким образом, что среднее время на перестановку будет постоянным. Помимо того, что этот алгоритм прост и эффективен с точки зрения вычислений, он имеет то преимущество, что последующие вычисления для сгенерированных перестановок могут быть ускорены за счет использования сходства между последовательными перестановками. ^[1]

Алгоритм

Последовательность перестановок, сгенерированная алгоритмом Штейнхауса–Джонсона–Троттера, имеет естественную рекурсивную структуру, которая может быть сгенерирована рекурсивным алгоритмом. Однако фактический алгоритм Штейнхауса–Джонсона–Троттера не использует рекурсию, вместо этого вычисляя ту же последовательность перестановок простым итеративным методом. Более позднее улучшение позволяет ему работать за постоянное среднее время на перестановку.

Рекурсивная структура

Последовательность перестановок для заданного числа может быть сформирована из последовательности перестановок для путем помещения числа в каждую возможную позицию в каждой из более коротких перестановок. Алгоритм Штейнхауза–Джонсона–Троттера следует этой структуре: последовательность перестановок, которую он генерирует, состоит из блоков перестановок, так что внутри каждого блока перестановки согласуются относительно порядка чисел от 1 до и отличаются только позицией . Сами блоки упорядочены рекурсивно, согласно алгоритму Штейнхауза–Джонсона–Троттера для одного элемента меньше. Внутри каждого блока позиции, в которые помещается , происходят либо в порядке убывания, либо в порядке возрастания, и блоки чередуются между этими двумя порядками: размещения в первом блоке находятся в порядке убывания, во втором блоке они находятся в порядке возрастания, в третьем блоке они находятся в порядке убывания и так далее. ^[2] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Таким образом, из единственной перестановки одного элемента,

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

Тот же шаблон размещения, чередующийся между убывающим и возрастающим размещением , применяется для любого большего значения . ^[2] В последовательностях перестановок с этой рекурсивной структурой каждая перестановка отличается от предыдущей либо перемещением на одну позицию за раз , либо изменением двух меньших чисел, унаследованных от предыдущей последовательности более коротких перестановок. В любом случае это различие является просто транспозицией двух соседних элементов. Когда первый и последний элементы последовательности также отличаются только двумя соседними элементами (позициями чисел и ), что может быть доказано по индукции. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n>1}$ ${\displaystyle 1}$ ${\displaystyle 2}$

Эта последовательность может быть сгенерирована рекурсивным алгоритмом , который строит последовательность меньших перестановок, а затем выполняет все возможные вставки наибольшего числа в рекурсивно сгенерированную последовательность. ^[2] Тот же порядок перестановок может быть также описан эквивалентно как порядок, сгенерированный следующим жадным алгоритмом. ^[3] Начните с тождественной перестановки . Теперь многократно транспонируйте наибольшую возможную запись с записью слева или справа, так что на каждом шаге создается новая перестановка, которая ранее не встречалась в списке перестановок. Например, в случае, если последовательность начинается с , затем переворачивается со своим левым соседом, чтобы получить . С этого момента переворачивание с его правым соседом даст начальную перестановку , поэтому последовательность вместо этого переворачивается со своим левым соседом и приходит к и т. д. Направление транспозиции (влево или вправо) всегда однозначно определяется в этом алгоритме. Однако фактический алгоритм Штейнхауса–Джонсона–Троттера не использует рекурсию и не нуждается в отслеживании перестановок, с которыми он уже столкнулся. Вместо этого он вычисляет ту же последовательность перестановок простым итеративным методом . ${\displaystyle 1\;2\;\ldots \;n}$ ${\displaystyle n=3}$ ${\displaystyle 1\;2\;3}$ ${\displaystyle 3}$ ${\displaystyle 1\;3\;2}$ ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle 1\;2\;3}$ ${\displaystyle 3}$ ${\displaystyle 1}$ ${\displaystyle 3\;1\;2}$

Оригинальная версия

Как описывает Джонсон, алгоритм генерации следующей перестановки из заданной перестановки выполняет следующие шаги. ${\displaystyle \pi }$

• Для каждого от 1 до пусть будет позицией, в которой находится значение в перестановке . Если порядок чисел от 1 до в перестановке определяет четную перестановку , пусть в противном случае пусть . ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle x_{i}}$ ${\displaystyle i}$ ${\displaystyle \pi }$ ${\displaystyle i-1}$ ${\displaystyle \pi }$ ${\displaystyle y_{i}=x_{i}-1}$ ${\displaystyle y_{i}=x_{i}+1}$
• Найдите наибольшее число , для которого определяет допустимую позицию в перестановке , содержащей число, меньшее . Поменяйте местами значения в позициях и . ${\displaystyle i}$ ${\displaystyle y_{i}}$ ${\displaystyle \pi }$ ${\displaystyle i}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

Когда не найдено ни одного числа, удовлетворяющего условиям второго шага алгоритма, алгоритм достигает финальной перестановки последовательности и завершается. Эта процедура может быть реализована за время per permutation. ^[4] ${\displaystyle i}$ ${\displaystyle O(n)}$

Троттер дает альтернативную реализацию итеративного алгоритма для той же последовательности в слегка прокомментированной нотации АЛГОЛа 60. ^[5]

Поскольку этот метод генерирует перестановки, которые попеременно являются четными и нечетными, его можно легко модифицировать для генерации только четных перестановок или только нечетных перестановок: чтобы сгенерировать следующую перестановку той же четности из данной перестановки, просто примените одну и ту же процедуру дважды. ^[6]

Ускорение Эвена

Последующее усовершенствование Шимона Эвена обеспечивает улучшение времени работы алгоритма путем сохранения дополнительной информации для каждого элемента в перестановке: его положение и направление (положительное, отрицательное или нулевое), в котором он в данный момент движется (по сути, это та же информация, вычисленная с использованием четности перестановки в версии алгоритма Джонсона). Первоначально направление числа 1 равно нулю, а все остальные элементы имеют отрицательное направление:

1 −2 −3

На каждом шаге алгоритм находит наибольший элемент с ненулевым направлением и меняет его местами в указанном направлении:

1 −3 −2

Если это приводит к тому, что выбранный элемент достигает первой или последней позиции в перестановке, или если следующий элемент в том же направлении больше выбранного элемента, направление выбранного элемента устанавливается равным нулю:

3 1 −2

После каждого шага все элементы, большие выбранного элемента (который ранее имел нулевое направление), получают свои направления, установленные для указания движения к выбранному элементу. То есть, положительные для всех элементов между началом перестановки и выбранным элементом и отрицательные для элементов к концу. Таким образом, в этом примере после перемещения числа 2 число 3 снова становится помеченным направлением:

+3 2 1

Оставшиеся два шага алгоритма : ${\displaystyle n=3}$

2 +3 1

2 1 3

Когда все числа становятся неотмеченными, алгоритм завершается. ^[7]

Этот алгоритм занимает время для каждого шага, на котором наибольшее число для перемещения равно . Таким образом, обмены, включающие число, занимают только постоянное время; поскольку эти обмены составляют все, кроме части всех обменов, выполняемых алгоритмом, среднее время на сгенерированную перестановку также постоянно, даже если небольшое количество перестановок займет большее количество времени. ^[1] ${\displaystyle O(i)}$ ${\displaystyle n-i+1}$ ${\displaystyle n}$ ${\displaystyle 1/n}$

Более сложная версия той же процедуры без циклов , подходящая для функционального программирования, позволяет выполнять ее за постоянное время на перестановку в каждом случае; однако изменения, необходимые для устранения циклов из процедуры, делают ее на практике более медленной. ^[8]

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

Пермутоэдр

Множество всех перестановок элементов может быть геометрически представлено пермутоэдром , многогранником , образованным из выпуклой оболочки векторов , перестановок вектора . Хотя он определен таким образом в -мерном пространстве, на самом деле это -мерный многогранник; например, пермутоэдр на четырех элементах является трехмерным многогранником, усеченным октаэдром . Если каждая вершина пермутоэдра помечена обратной перестановкой к перестановке, определенной ее координатами вершин, результирующая маркировка описывает граф Кэли симметричной группы перестановок на элементах, как это генерируется перестановками, которые меняют местами соседние пары элементов. Таким образом, каждые две последовательные перестановки в последовательности, сгенерированной алгоритмом Штейнхауза–Джонсона–Троттера, соответствуют таким образом двум вершинам, которые образуют конечные точки ребра в пермутоэдре, и вся последовательность перестановок описывает гамильтонов путь в пермутоэдре, путь, который проходит через каждую вершину ровно один раз. Если последовательность перестановок завершается добавлением еще одного ребра из последней перестановки к первому в последовательности, результатом вместо этого является гамильтонов цикл. ^[9] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle (1,2,\dots n)}$ ${\displaystyle n}$ ${\displaystyle (n-1)}$ ${\displaystyle n}$

Коды Грея

Код Грея для чисел в заданном основании — это последовательность, которая содержит каждое число до заданного предела ровно один раз, таким образом, что каждая пара последовательных чисел отличается на единицу в одной цифре. Перестановки чисел от 1 до можно поставить во взаимно-однозначное соответствие с числами от 0 до, соединив каждую перестановку с последовательностью чисел , которые подсчитывают количество позиций в перестановке, которые находятся справа от значения и содержат значение меньше (то есть количество инверсий, для которых является большим из двух инвертированных значений), а затем интерпретируя эти последовательности как числа в факториальной системе счисления , то есть смешанной системе счисления с последовательностью оснований Например, перестановка даст значения , , , , и . Последовательность этих значений , дает число Последовательные перестановки в последовательности, сгенерированной алгоритмом Штейнхауза–Джонсона–Троттера, имеют количество инверсий, которое отличается на единицу, образуя код Грея для факториальной системы счисления. ^[10] ${\displaystyle n!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n!-1}$ ${\displaystyle c_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle (1,2,3,4,\dots )}$ ${\displaystyle (3,1,4,5,2)}$ ${\displaystyle c_{1}=0}$ ${\displaystyle c_{2}=0}$ ${\displaystyle c_{3}=2}$ ${\displaystyle c_{4}=1}$ ${\displaystyle c_{5}=1}$ ${\displaystyle (0,0,2,1,1)}$ $${\displaystyle 0\times 0!+0\times 1!+2\times 2!+1\times 3!+1\times 4!=34.}$$

В более общем смысле исследователи комбинаторных алгоритмов определили код Грея для набора комбинаторных объектов как упорядочение объектов, в котором каждые два последовательных объекта отличаются минимально возможным образом. В этом обобщенном смысле алгоритм Штейнхауса-Джонсона-Троттера генерирует код Грея для самих перестановок. ^[11]

История

Метод был известен большую часть своей истории как метод смены звона церковных колоколов: он дает процедуру, с помощью которой набор колоколов может быть прозвонен через все возможные перестановки, изменяя порядок только двух колоколов за смену. Эти так называемые «простые смены» или «простая охота» были известны около 1621 года для четырех колоколов, ^[12] и общий метод был прослежен до неопубликованной рукописи 1653 года Питера Манди . ^[6] Книга 1677 года Фабиана Стедмана перечисляет решения для шести колоколов. ^[13] Совсем недавно звонари, меняющие звон, соблюдали правило, что ни один колокол не может оставаться в одном и том же положении в течение трех последовательных перестановок; это правило нарушается простыми заменами, поэтому были разработаны другие стратегии, которые меняют несколько колоколов за смену. ^[14]

Алгоритм назван в честь Хьюго Штейнхауза , Сельмера М. Джонсона и Хейла Ф. Троттера . Джонсон и Троттер заново открыли алгоритм независимо друг от друга в начале 1960-х годов. ^[15] Книга Штейнхауза 1958 года, переведенная на английский язык в 1964 году, описывает связанную невозможную головоломку генерации всех перестановок системой частиц, каждая из которых движется с постоянной скоростью вдоль линии и меняет позиции, когда одна частица обгоняет другую. ^[16] В статье 1976 года Ху и Бьен приписывают Штейнхаузу формулировку алгоритмической проблемы генерации всех перестановок, ^[17] и к 1989 году его книга была (неправильно) приписана как одна из оригинальных публикаций алгоритма. ^[18]

Смотрите также

• Алгоритм Хипа , другой метод перечисления всех перестановок
• Перетасовка Фишера-Йетса , метод генерации случайных перестановок

Примечания

1. Седжвик (1977).
2. Ленстра и Риннуй Кан (1979); Сэвидж (1997), раздел 3; Птица (2010).
3. Уильямс (2013).
4. Джонсон (1963).
5. Троттер (1962).
6. Knuth (2011).
7. Эвен (1973).
8. Эрлих (1973); Дершовиц (1975); Седжвик (1977); Птица (2010).
9. См., например, раздел 11 Savage (1997).
10. Дейкстра (1976); Кнут (2011).
11. Сэвидж (1997).
12. Уайт (1996).
13. Стедман (1677); списки простых изменений для шести колоколов см. на стр. 48–80.
14. Макгуайр (2003); Кнут (2011).
15. Джонсон (1963); Троттер (1962).
16. Штейнхаус (1964).
17. Ху и Тянь (1976).
18. Раски (1989).

Ссылки

• Берд, Ричард (2010), «Глава 29: Алгоритм Джонсона–Троттера», Pearls of Functional Algorithm Design , Cambridge University Press, стр. 251–257, doi :10.1017/cbo9780511763199, ISBN 9780511763199
• Дершовиц, Нахум (1975), «Упрощенный алгоритм без циклов для генерации перестановок», Nordisk Tidskr. Informationsbehandling (BIT) , 15 (2): 158–164, doi :10.1007/bf01932689, MR  0502206, S2CID  121353303
• Дейкстра, Эдсгер В. (1976), «На вызов, брошенный Дэвидом Грайсом» (PDF) , Acta Informatica , 6 (4): 357–359, doi :10.1007/BF00268136, MR  0426492, S2CID  7085805. Хотя Дейкстра не ссылается на какую-либо предшествующую литературу, более ранний черновик EWD502 показывает, что он знал Троттера (1962).
• Эрлих, Гидеон (1973), «Бесциклические алгоритмы для генерации перестановок, комбинаций и других комбинаторных конфигураций», Журнал ACM , 20 (3): 500–513, doi : 10.1145/321765.321781 , S2CID  21493963
• Даже, Шимон (1973), Алгоритмическая комбинаторика , Macmillan
• Ху, TC ; Тиен, BN (октябрь 1976 г.), «Создание перестановок с неразличимыми элементами», The American Mathematical Monthly , 83 (8): 629–631, doi :10.1080/00029890.1976.11994195, JSTOR  2319890
• Джонсон, Селмер М. (1963), «Создание перестановок смежной транспозицией», Математика вычислений , 17 (83): 282–285, doi : 10.1090/S0025-5718-1963-0159764-2 , JSTOR  2003846, MR  0159764
• Lenstra, JK ; Rinnooy Kan, AHG (сентябрь 1979 г.), «Рекурсивный подход к реализации перечислительных методов», Труды Школы анализа и проектирования алгоритмов в комбинаторной оптимизации, Удине, Италия (PDF) , Технический отчет 8003/0, Университет Эразма Роттердамского; см. раздел 2.1, «Генератор минимальных изменений», стр. 3–8
• Кнут, Дональд (2011), «Раздел 7.2.1.2: Генерация всех перестановок», Искусство программирования, том 4A: Комбинаторные алгоритмы, часть 1
• МакГвайр, Гэри (2003), Звонки, мотели и группы перестановок , CiteSeerX  10.1.1.6.5544
• Раски, Фрэнк (1989), «Генерация транспозиции чередующихся перестановок», Order , 6 (3): 227–233, doi :10.1007/BF00563523, MR  1048093
• Сэвидж, Карла (1997), «Обзор комбинаторных кодов Грея», SIAM Review , 39 (4): 605–629, Bibcode : 1997SIAMR..39..605S, CiteSeerX  10.1.1.39.1924 , doi : 10.1137/S0036144595295272, JSTOR  2132693, MR  1491049
• Седжвик, Роберт (1977), «Методы генерации перестановок», ACM Comput. Surv. , 9 (2): 137–164, doi : 10.1145/356689.356692 , S2CID  12139332
• Стедман, Фабиан (1677), Кампания, или Искусство звона, усовершенствованное, Лондон: W. Godbid – через Early English Books Online Text Creation Partnership
• Штейнхаус, Хьюго (1964), Сто задач по элементарной математике , Нью-Йорк: Basic Books, стр. 49–50, MR  0157881
• Троттер, Х. Ф. (август 1962 г.), «Алгоритм 115: Perm», Сообщения ACM , 5 (8): 434–435, doi : 10.1145/368637.368660 , S2CID  1013826
• Уайт, Артур Т. (ноябрь 1996 г.), «Фабиан Стедман: первый теоретик групп?», The American Mathematical Monthly , 103 (9): 771–778, doi :10.1080/00029890.1996.12004816, JSTOR  2974446
• Williams, Aaron (2013), "Жадный алгоритм кода Грея", в Dehne, Frank; Solis-Oba, Roberto; Sack, Jörg-Rüdiger (ред.), Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, 12-14 августа 2013 г. Труды , Lecture Notes in Computer Science, т. 8037, Springer, стр. 525–536, doi :10.1007/978-3-642-40104-6_46