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

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

Перестановки четырех элементов, основанные на их элементах инверсия наборы (наборы пар элементов вне их естественного порядка), векторы инверсии и числа инверсии

Наборы инверсии образуют код Грея, поэтому также векторы инверсии (суммы восходящих диагоналей треугольников) и числа инверсии.

Цифры слева - это обратные перестановки. колексикографический индексы (сравнивать список в естественном порядке ) и сформируем четвертый ряд треугольника OEIS: A280319

Наборы инверсии перестановок на расстоянии 12 мест друг от друга равны дополняет.

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

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

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

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

Последовательность перестановок для данного числа п может быть сформирована из последовательности перестановок для п - 1, поместив число п в каждую возможную позицию в каждой из более коротких перестановок. Когда перестановка на п - 1 шт. даже перестановка (как и в случае первой, третьей и т. д. перестановок в последовательности), тогда число п размещается во всех возможных позициях в порядке убывания, начиная с п до 1; когда перестановка на п - 1 товар нечетный, количество п размещается во всех возможных позициях в порядке возрастания.^[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

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

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

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

Алгоритм

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

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

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

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

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

Даже ускорение

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

1 −2 −3

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

1 −3 −2

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

3 1 −2

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

+3 2 1

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

2 +3 1

2 1 3

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

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

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

Геометрическая интерпретация

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

Связь с кодами Грея

А Код Грея для чисел в данном основание представляет собой последовательность, которая содержит каждое число до заданного предела ровно один раз, таким образом, что каждая пара последовательных чисел отличается на единицу одной цифрой. В п! перестановки п числа от 1 до п могут быть поставлены во взаимно однозначное соответствие с п! числа от 0 до п! - 1, сочетая каждую перестановку с последовательностью чисел c_я которые подсчитывают количество позиций в перестановке, которые находятся справа от значения я и которые содержат значение меньше, чемя (то есть количество инверсии для которого я является большим из двух инвертированных значений), а затем интерпретируя эти последовательности как числа в факториальная система счисления, это смешанный корень система с основанием системы счисления (1,2,3,4, ...). Например, перестановка (3,1,4,5,2) даст значения c₁ = 0, c₂ = 0, c₃ = 2, c₄ = 1 и c₅ = 1. Последовательность этих значений (0,0,2,1,1) дает число

0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

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

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

История

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

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

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

• Алгоритм кучи
• Перемешивание Фишера – Йетса

Примечания

Рекомендации