Введение
Алгоритм Штейнхауза–Джонсона–Троттера или алгоритм Джонсона–Троттера, также называемый простыми перестановками, — это алгоритм, названный в честь Хьюго Штейнхауза, Селмера М. Джонсона и Хейла Ф. Троттера, который генерирует все перестановки элементов. Каждая пара соседних перестановок в полученной последовательности отличается обменом двух соседних элементов перестановки. Эквивалентно, этот алгоритм находит гамильтонов цикл в пермутоэдре — многограннике, вершины которого представляют перестановки, а рёбра — обмены. Этот метод был известен ещё английским мастерам переменного звона в XVII веке, а Роберт Седжвик называет его «возможно, самым известным алгоритмом перечисления перестановок». Версию алгоритма можно реализовать таким образом, чтобы среднее время на генерацию перестановки было постоянным. Помимо простоты и вычислительной эффективности, этот алгоритм имеет преимущество в том, что последующие вычисления с генерируемыми перестановками могут быть ускорены за счёт использования сходства между соседними перестановками.
Алгоритм
Последовательность перестановок, генерируемых алгоритмом Штейнхауза — Джонсона — Троттера, обладает естественной рекурсивной структурой, которую можно получить с помощью рекурсивного алгоритма. Однако сам алгоритм Штейнхауза — Джонсона — Троттера не использует рекурсию, а вместо этого вычисляет ту же последовательность перестановок простым итеративным методом. Последующее улучшение позволяет ему выполняться в среднем за постоянное время на перестановку.
Пермутоэдр
Множество всех перестановок элементов может быть геометрически представлено пермутоэдром — политопом, образованным выпуклой оболочкой векторов, являющихся перестановками исходного вектора. Хотя он и определяется таким образом в n-мерном пространстве, фактически это (n-1)-мерный политоп; например, пермутоэдр для четырех элементов является трехмерным полиэдром, усеченным октаэдром. Если каждой вершине пермутоэдра присвоить обратную перестановку к перестановке, определяемой координатами этой вершины, то полученная маркировка описывает граф Кэли симметрической группы перестановок на n элементах, порожденный перестановками, меняющими местами соседние пары элементов. Таким образом, любые две последовательные перестановки в последовательности, сгенерированной алгоритмом Штейнхауса — Джонсона — Троттера, соответствуют двум вершинам, являющимся концами ребра пермутоэдра, а вся последовательность перестановок описывает гамильтонов путь в пермутоэдре — путь, проходящий через каждую вершину ровно один раз. Если последовательность перестановок замкнуть, добавив ребро от последней перестановки к первой, то получится гамильтонов цикл.
Серые коды
Код Грея для чисел в заданной системе счисления — это последовательность, содержащая каждое число до заданного предела ровно один раз, таким образом, что каждая пара последовательных чисел отличается в одной единственной цифре. Пермутации чисел от 1 до *n* можно привести в соответствие одно к одному с числами от 0 до *n*-1, сопоставив каждой перестановке последовательность чисел, подсчитывающих количество позиций в перестановке, находящихся справа от значения *i* и содержащих значение, меньшее *i* (то есть количество инверсий, для которых *i* является большим из двух перевернутых значений), а затем интерпретируя эти последовательности как числа в факториальной системе счисления, то есть в смешанной системе счисления с последовательностью оснований 1, 2, 3, … *n*. Например, для перестановки 3, 1, 4, 2, 5 значениями будут 0, 1, 2, 3, 4, а последовательность этих значений 0, 1, 2, 3, 4 дает число 23.
Последовательные перестановки в последовательности, генерируемой алгоритмом Стейнхауса — Джонсона — Троттера, имеют количество инверсий, отличающееся на единицу, формируя код Грея для факториальной системы счисления. В более общем смысле, исследователи комбинаторных алгоритмов определяют код Грея для набора комбинаторных объектов как упорядочение объектов, в котором каждый два последовательных объекта отличаются минимально возможным образом. В этом обобщенном смысле алгоритм Стейнхауса — Джонсона — Троттера генерирует код Грея для самих перестановок.
История
Метод на протяжении большей части своей истории был известен как метод перезвона церковных колоколов: он предоставляет процедуру, с помощью которой набор колоколов может быть прозвонен во всех возможных перестановках, меняя порядок только двух колоколов за каждый удар. Эти так называемые "простые перестановки" или "простой перебор" были известны примерно с 1621 года для четырех колоколов, а общий метод был прослежен до неопубликованной рукописи 1653 года, написанной Питером Манди. Книга Фабиана Стетмана 1677 года содержит решения для колоколов количеством до шести. В последнее время перезвонщики придерживаются правила, согласно которому ни один колокол не должен оставаться в одном и том же положении в течение трех последовательных перестановок; это правило нарушается простыми перестановками, поэтому были разработаны другие стратегии, которые меняют местами несколько колоколов за один удар. Алгоритм назван в честь Хьюго Стейнхауса, Селмера М. Джонсона и Хейла Ф. Троттера. Джонсон и Троттер независимо друг от друга заново открыли алгоритм в начале 1960-х годов. Книга Стейнхауса 1958 года, переведенная на английский язык в 1964 году, описывает связанную с ней неразрешимую задачу генерации всех перестановок системой частиц, каждая из которых движется с постоянной скоростью по прямой и меняет положение, когда одна частица обгоняет другую. В статье Ху и Биена 1976 года Стейнхаусу приписывается формулировка алгоритмической задачи генерации всех перестановок, а к 1989 году его книга была (неверно) указана как одна из первых публикаций, описывающих этот алгоритм.