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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 −2 −3

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

1 −3 −2

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

3 1 −2

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

+3 2 1

Остальные два шага алгоритма $n=3$ являются:

2 +3 1

2 1 3

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

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

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

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

Пермутоэдр

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

Коды Грея

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

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

История

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

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

См. также

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

Примечания

^ Jump up to: ^а ^б ^с Седжвик (1977) .
^ Jump up to: ^а ^б ^с Ленстра и Ринной Кан (1979) ; Сэвидж (1997) , раздел 3; Птица (2010) .
^ Уильямс (2013) .
^ Джонсон (1963) .
^ Троттер (1962) .
^ Jump up to: ^а ^б Кнут (2011) .
^ Эвен (1973) .
^ Честный (1973) ; Дершовиц (1975) ; Седжвик (1977) ; Птица (2010) .
^ См., например, раздел 11 Savage (1997) .
^ Дейкстра (1976) ; Кнут (2011) .
^ Сэвидж (1997) .
^ Белый (1996) .
^ Стедман (1677) ; списки простых изменений для колоколов (до шести штук) см. на стр. 48–80.
^ Макгуайр (2003) ; Кнут (2011) .
^ Джонсон (1963) ; Троттер (1962) .
^ Каменный дом (1964) .
^ Ху и Тьен (1976) .
^ Раски (1989) .

Ссылки

Берд, Ричард (2010), «Глава 29: Алгоритм Джонсона-Троттера», Pearls of Functional Algorithm Design , Cambridge University Press, стр. 251–257, doi : 10.1017/cbo9780511763199 , ISBN 9780511763199
Дершовиц, Нахум (1975), «Упрощенный алгоритм без петель для генерации перестановок», Nordisk Tidskr. Обработка информации (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), «Безцикловые алгоритмы для генерации перестановок, комбинаций и других комбинаторных конфигураций», Journal of the ACM , 20 (3): 500–513, doi : 10.1145/321765.321781 , S2CID 21493963
Эвен, Шимон (1973), Алгоритмическая комбинаторика , Макмиллан
Ху, ТК ; Тьен, Б.Н. (октябрь 1976 г.), «Генерация перестановок с неразличимыми элементами», The American Mathematical Monthly , 83 (8): 629–631, doi : 10.1080/00029890.1976.11994195 , JSTOR 2319890
Джонсон, Селмер М. (1963), «Генерация перестановок путем смежной транспозиции», Mathematics of Computation , 17 (83): 282–285, doi : 10.1090/S0025-5718-1963-0159764-2 , JSTOR 2003846 , MR 0159764
Ленстра, JK ; Риннуй Кан, 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/С0036144595295272 , ДЖСТОР 2132693 , МР 1491049
Седжвик, Роберт (1977), «Методы генерации перестановок», ACM Comput. Выж. , 9 (2): 137–164, doi : 10.1145/356689.356692 , S2CID 12139332
Стедман, Фабиан (1677), Кампаналогия, или Улучшенное искусство звонка , Лондон: В. Годбид - через Партнерство по созданию текста в Интернете Early English Books
Стейнхаус, Хьюго (1964), Сто задач по элементарной математике , Нью-Йорк: Basic Books, стр. 49–50, MR 0157881.
Троттер, HF (август 1962 г.), «Алгоритм 115: Пермь», Communications of 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
Уильямс, Аарон (2013), «Алгоритм жадного кода Грея», Дене, Франк; Солис-Оба, Роберто; Сак, Йорг-Рюдигер (ред.), «Алгоритмы и структуры данных — 13-й международный симпозиум», WADS 2013, Лондон, Онтарио, Канада, 12–14 августа 2013 г. Труды , конспекты лекций по информатике, том. 8037, Springer, стр. 525–536, номер документа : 10.1007/978-3-642-40104-6_46.

[FOOTNOTESedgewick1977-1] Jump up to: ^а ^б ^с Седжвик (1977) .

[recursive-2] Jump up to: ^а ^б ^с Ленстра и Ринной Кан (1979) ; Сэвидж (1997) , раздел 3; Птица (2010) .

[FOOTNOTEWilliams2013-3] Уильямс (2013) .

[FOOTNOTEJohnson1963-4] Джонсон (1963) .

[FOOTNOTETrotter1962-5] Троттер (1962) .

[FOOTNOTEKnuth2011-6] Jump up to: ^а ^б Кнут (2011) .

[FOOTNOTEEven1973-7] Эвен (1973) .

[8] Честный (1973) ; Дершовиц (1975) ; Седжвик (1977) ; Птица (2010) .

[9] См., например, раздел 11 Savage (1997) .

[10] Дейкстра (1976) ; Кнут (2011) .

[FOOTNOTESavage1997-11] Сэвидж (1997) .

[FOOTNOTEWhite1996-12] Белый (1996) .

[13] Стедман (1677) ; списки простых изменений для колоколов (до шести штук) см. на стр. 48–80.

[14] Макгуайр (2003) ; Кнут (2011) .

[15] Джонсон (1963) ; Троттер (1962) .

[FOOTNOTESteinhaus1964-16] Каменный дом (1964) .

[FOOTNOTEHuTien1976-17] Ху и Тьен (1976) .

[FOOTNOTERuskey1989-18] Раски (1989) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]