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

Гамильтониан цикл в графе Кэли симметрической группы, сгенерированной алгоритмом Штейнхауса – Джонсона – Троттера Перестановки четырех элементов, их инверсия на основе элементов устанавливает (наборы пар элементов вне их естественного порядка), векторы инверсии и числа инверсии.. Наборы инверсии образуют код Грея, таким образом, также вектор инверсии s (суммы восходящих диагоналей треугольников) и числа инверсии... Числа слева - это обратные колексикографические индексы перестановок (сравните перечислить в естественном порядке ) и сформировать строку 4 треугольника OEIS : A280319.. Наборы инверсии перестановок, расположенных на расстоянии 12 позиций друг от друга, являются дополнениями. Колесная диаграмма всех перестановок длины $n\; =\; 4\; \{\backslash \; displaystyle\; n\; =\; 4\}$, сгенерированная алгоритмом Штейнхауса-Джонсона-Троттера, где каждая перестановка имеет цветовую кодировку (1 = синий, 2 = зеленый, 3 = желтый, 4 = красный).

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

. Этот метод был известен уже в 17-м веке английским звонилкам и Седжуику (1977). называет его «пожалуй, наиболее известным алгоритмом перебора перестановок». Помимо простоты и эффективности вычислений, он имеет то преимущество, что последующие вычисления генерируемых им перестановок могут быть ускорены, поскольку эти перестановки очень похожи друг на друга.

• 1 Рекурсивная структура
• 2 Алгоритм
• 3 Ускорение Эвена
• 4 Геометрическая интерпретация
• 5 Связь с кодами Грея
• 6 История
• 7 См. Также
• 8 Примечания
• 9 Ссылки

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

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

1

можно разместить число 2 в каждой возможной позиции в порядке убывания, чтобы сформировать список из двух перестановок на двух элементах,

1 2

21

Затем можно поместить число 3 в каждую из трех разных позиций для этих двух перестановок в порядке убывания для первой перестановки 1 2, а затем в порядке возрастания для перестановки 2 1:

1 2 3

1 32

31 2

32 1

2 31

2 1 3

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

Хотя эта последовательность может быть сгенерирована с помощью рекурсивного алгоритма, который конструирует последовательность меньших перестановок и затем выполняет все возможные вставки наибольшего числа в рекурсивно сгенерированную последовательность, реальный Steinhaus– Алгоритм Джонсона – Троттера избегает рекурсии, вместо этого вычисляя ту же последовательность перестановок итерационным методом.

Существует эквивалентное и несколько более простое в концептуальном плане определение порядка перестановок Штейнхауза-Джонсона-Троттера с помощью следующего жадного алгоритма: Начнем с тождественной перестановки $1\; 2\dots \; n\; \{\backslash \; displaystyle\; 1\; \backslash ;\; 2\; \backslash ;\; \backslash \; ldots\; \backslash ;\; n\}$. Теперь мы многократно перемещаем максимально возможную запись с записью влево или вправо, так что на каждом шаге создается новая перестановка, которая ранее не встречалась в списке перестановок. Например, в случае $n\; =\; 3\; \{\backslash \; displaystyle\; n\; =\; 3\}$мы начинаем с 123, затем переворачиваем 3 с его левым соседом и получаем 132. Затем мы переворачиваем 3 с его левым соседом. 1, поскольку переворот 3 с его правым соседом 2 снова даст 123, что мы видели раньше, поэтому мы приходим к 312 и т. Д. Направление транспозиции (влево или вправо) всегда однозначно определяется в этом алгоритме.

Как описано Johnson (1963), алгоритм генерации следующей перестановки из данной перестановки π выполняет следующие шаги

• Для каждого i из От 1 до n, пусть x i будет позицией, в которой значение i помещается в перестановку π. Если порядок чисел от 1 до i - 1 в перестановке π определяет четную перестановку, пусть y i = x i - 1; в противном случае пусть y i = x i + 1.
• Найдите наибольшее число i, для которого y i определяет допустимую позицию в перестановке π, который содержит число меньше i. Поменяйте местами значения в позициях x i и y i.

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

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

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

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

1 −2 −3

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

1 −3 −2

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

3 1 −2

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

+3 2 1

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

2 + 3 1

2 1 3

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

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

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

Набор всех перестановок n элементов может быть геометрически представлен пермутоэдром, многогранник , образованный из выпуклой оболочки числа n! векторы, перестановки вектора (1,2,... n). Несмотря на то, что он определен таким образом в n-мерном пространстве, на самом деле это (n - 1) -мерный многогранник; например, пермутоэдр на четырех элементах представляет собой трехмерный многогранник, усеченный октаэдр. Если каждая вершина пермутоэдра помечена перестановкой, обратной перестановке, определенной ее координатами вершины, полученная разметка описывает граф Кэли симметрической группы перестановок на n элементах, генерируемых перестановками, которые меняют местами соседние пары элементов. Таким образом, каждые две последовательные перестановки в последовательности, генерируемой алгоритмом Штейнхауса – Джонсона – Троттера, соответствуют двум вершинам, которые образуют концы ребра в пермутоэдре, а вся последовательность перестановок описывает гамильтонов путь в пермутоэдре - путь, который проходит через каждую вершину ровно один раз. Если последовательность перестановок завершается добавлением еще одного ребра из последней перестановки к первой в последовательности, то вместо этого получается гамильтонов цикл.

A Код Грея для чисел с заданным основанием - это последовательность, которая содержит каждое число до заданного предела ровно один раз, таким образом, что каждая пара последовательных чисел отличается на единицу в одной цифре. Затем! перестановки n чисел от 1 до n могут быть помещены во взаимно однозначное соответствие с n! числа от 0 до n! - 1 путем объединения каждой перестановки в пару с последовательностью чисел c i, которые подсчитывают количество позиций в перестановке, которые находятся справа от значения i и содержат значение меньше i (то есть число инверсий, для которых i - большее из двух инвертированных значений), а затем интерпретировать эти последовательности как числа в факториальной системе счисления, то есть смешанном основании система с основанием (1,2,3,4,...). Например, перестановка (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 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

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

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

Алгоритм назван в честь Хьюго Штейнхауса, Селмера М. Джонсона и Хейла Ф. Троттера. Джонсон и Троттер открыли алгоритм независимо друг от друга в начале 1960-х годов. Книга Штейнхауса, первоначально опубликованная в 1958 году и переведенная на английский язык в 1963 году, описывает связанную загадку генерации всех перестановок системой частиц, каждая из которых движется с постоянной скоростью вдоль линии и меняет позиции, когда одна частица догоняет другую. Никакое решение невозможно для n>3, потому что количество перестановок намного меньше, чем количество перестановок, но алгоритм Штейнхауса – Джонсона – Троттера описывает движение частиц с непостоянными скоростями, которые генерируют все перестановки.

Вне математики тот же метод был известен гораздо дольше как метод изменения звонка церковных колоколов: он дает процедуру, с помощью которой набор колоколов может быть перебран через все возможные перестановки, изменяя порядок только двух звонков за изменение. Эти так называемые «простые изменения» были зарегистрированы еще в 1621 году для четырех колоколов, а в книге 1677 года Фабиана Стедмана перечислены решения для шести колоколов. В последнее время меняющие звонари соблюдают правило, согласно которому ни один звонок не может оставаться в одном и том же положении в течение трех последовательных перестановок; это правило нарушается простыми изменениями, поэтому были разработаны другие стратегии, которые меняют местами несколько колокольчиков для каждого изменения.

• алгоритм Кучи
• перемешивание Фишера – Йейтса