Алгоритм Джонсона — Троттера

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

Перестановки четырёх элементов, их множества инверсий (множества пар элементов, нарушающие натуральный порядок), вектора инверсий и числа инверсий.
Множества инверсий образуют код Грея.
Числа слева — обратные колексикографиеческие индексы (сравните с списком в естественном порядке), они образуют строку в треугольнике A280319.
Строки на расстоянии 12 друг от друга являются дополнительными.

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

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

Этот метод был известен уже в XVII веке — он использовался в распространённом в англиканской церкви виде колокольного перезвона под названием change ringing, и Седжвик назвал его «возможно самым известным алгоритмом перечисления перестановок». Алгоритм можно реализовать таким образом, что время на создание каждой отдельной перестановки будет постоянным. Будучи простым и одновременно вычислительно эффективным, этот алгоритм имеет преимущество, что вычисления на перестановках, которые образует алгоритм, можно ускорить ввиду похожести соседних перестановок.

Алгоритм

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

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

Последовательность перестановок для заданного числа $n$ может быть образована из последовательности перестановок для $n-1$ путём размещения числа $n$ во все возможные позиции каждой из более коротких перестановок. Алгоритм Джонсона — Троттера следует следующей структуре: последовательность перестановок, которые он образует, состоит из $(n-1)!$ блоков перестановок, так что внутри каждого блока перестановок сохраняется порядок чисел от 1 до $n-1$ и перестановки отличаются только положением числа $n$. Сами блоки упорядочены рекурсивно согласно алгоритму Джонсона — Троттера для набора без одного элемента. Внутри каждого блока положения, в котором находится число $n$, идут в убывающем или возрастающем порядке, меняя порядок с каждым следующим блоком. Позиции числа $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

Продолжаем ту же процедуру для последующих значений $n$, меняя убывающий и возрастающий порядок с каждой перестановкой. В последовательности перестановок в этой рекурсивной структуре каждая перестановка отличается от предыдущей позицией $n$ или меняются два меньших числа, унаследованных от предыдущей последовательности более коротких перестановок. В любом случае перестановки отличаются лишь обменом местами двух соседних элементов. Если $n>1$, первая и последняя перестановки в последовательности отличаются лишь двумя соседними элементами (в позициях $1$ и $2$), что можно доказать по индукции.

Эту последовательность можно получить с помощью рекурсивного алгоритма, который создаёт последовательность перестановок меньшего размера, а затем осуществляет все возможные вставки наибольшего числа в созданную рекурсивно последовательность. Тот же самый порядок перестановок может быть описан как порядок, образованный следующим жадным алгоритмом. Начинаем с тождественной перестановки $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)$ на перестановку.

Троттер дал альтернативную реализацию итеративного алгоритма для той же последовательности с комментариями в стиле ALGOL 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$, занимает постоянное время. since these swaps account for all but a $1/n$ fraction of all of the swaps performed алгоритмом, the average time per перестановку generated is also constant, even though a small number of перестановок will take a larger amount of time.

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

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

Перестановочный многогранник

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

Коды Грея

Код Грея для чисел с заданным основанием — это последовательность, которая содержит каждое число до указанного предела ровно один раз, и в этой последовательности каждая пара последовательных чисел отличаются одной цифрой. $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.$$

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

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

История

Алгоритм назван именами Селмера М. Джонсона и Хейла Ф. Троттера. Джонсон и Троттер создали алгоритм независимо друг от друга в начале 1960-х годов.

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

См. также

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