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

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

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

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

Алгоритм Джонсона — Троттера (Штейнгауса — Джонсона — Троттера) — алгоритм, генерирующий все перестановки $n$ элементов, на каждом шаге проводящий обмен местами двух соседних элементов. Эквивалентно — алгоритм находит гамильтонов цикл в перестановочном многограннике.

Назван по именам Селмера Джонсона и Хейла Троттера, описавших алгоритм в 1962—1963 годах, однако фактически метод тривиален и известен издавна, например, с XVII века используется в распространённом в англиканской церкви колокольном перезвоне под названием Шаблон:Нп5Шаблон:Sfn. Алгоритм можно реализовать таким образом, что время на создание каждой отдельной перестановки будет постоянным. Будучи простым и одновременно вычислительно эффективным, этот алгоритм имеет преимущество, что вычисления на перестановках, которые образует алгоритм, можно ускорить ввиду похожести соседних перестановокШаблон:Sfn.

Алгоритм

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

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

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

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

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$), что можно доказать по индукции.

Эту последовательность можно получить с помощью рекурсивного алгоритма, который создаёт последовательность перестановок меньшего размера, а затем осуществляет все возможные вставки наибольшего числа в созданную рекурсивно последовательностьШаблон:SfnШаблон:Sfn. Тот же самый порядок перестановок может быть описан как порядок, образованный следующим жадным алгоритмомШаблон:Sfn. Начинаем с тождественной перестановки $12\dots n$. Теперь последовательно переставляем наибольший элемент с левым или правым элементом так, что на каждом шаге образуется новая перестановка, которая не встречалась в списке перестановок до этого. Например, в случае $n=3$ последовательность начинается с $123$, затем переставляется $3$ с левым соседом что приводит к $132$. В этом месте перестановка $3$ с правым соседом $2$ приведёт к начальной перестановке $123$, так что снова переставим $3$ с левым соседом $1$ и получаем $312$, и так далее. Направление обмена позиций (слева или справа) в алгоритме всегда определяется однозначно. Однако действительный алгоритм Джонсона — Троттера не использует рекурсию и не требует хранения списка созданных перестановок. Вместо этого алгоритм вычисляет ту же последовательность перестановок простым итеративным методом.

Исходная версия

Согласно варианту ДжонсонаШаблон:Sfn, алгоритм создания следующей перестановки из заданной перестановки $\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)$ на перестановку.

ТроттерШаблон:Sfn дал альтернативную реализацию итеративного алгоритма для той же последовательности с комментариями в стиле Алгола-60.

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

Ускорение алгоритма Ивеном

Улучшение алгоритма Шимоном Ивеном даёт улучшение времени выполнения путём запоминания дополнительной информации для каждого элемента в перестановке — его позицию и направление (положительное, отрицательное или нулевое), в котором элемент движется (по существу, это та же информация, которая вычисляется с помощью чётности перестановки в версии алгоритма Джонсона). Начально направление числа 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$ части от всех операций обмена, выполняемых алгоритмом, среднее время на перестановку постоянно, даже если некоторое небольшое количество перестановок занимает бо́льшее времяШаблон:Sfn.

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

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

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

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

Коды Грея

Код Грея для чисел с заданным основанием — это последовательность, которая содержит каждое число до указанного предела ровно один раз, и в этой последовательности каждая пара последовательных чисел отличаются одной цифрой. $n!$ перестановок $n$ чисел от 1 до $n$ могут быть расположены в соответствии один-к-одному с $n!$ числами от 0 до $n!-1$ путём связывания каждой перестановки с последовательностью чисел $c_i$, которые соответствуют числу позиций в перестановке, находящихся справа от значения $i$ и содержащих значение, меньшее $i$ (то есть, число инверсий для каждого $i$), затем эти последовательности как числа в факториальной системе счисления, то есть в Шаблон:Нп5 с последовательностью оснований $(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$.

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

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

См. также

• Шаблон:Нп5 — другой метод перечисления всех перестановок
• Тасование Фишера — Йетса — метод создания случайных перестановок

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга; см. Section 2.1, «A minimum-change generator», pp. 3-8
• Шаблон:Книга
  • Шаблон:Книга:Кнут
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга