Interested Article - Алгоритм Джонсона — Троттера
![](/images/007/914/7914025/1.jpg?rand=837227)
![](https://cdn.wafarin.com/avatars/38e18925d2a8e9c1df99bd4d6462af86.jpg)
- 2020-09-29
- 1
![](/images/007/914/7914025/1.jpg?rand=643209)
![](/images/007/914/7914025/2.jpg?rand=271321)
Множества инверсий образуют код Грея, thus also the inversion vectors (sums of the triangles' ascending diagonals) and inversion numbers.
Числа слева — обратные колексикографиеческие индексы (сравните с ) и образует строку and form row 4 of triangle
Строки на расстоянии 12 друг от друга являются дополнительными.
![](/images/007/914/7914025/3.jpg?rand=224642)
Алгоритм Джонсона — Троттера — это алгоритм , названный именами Селмера М. Джонсона и Хейла Ф. Троттера, который генерирует все перестановки элементов. Каждая перестановка в последовательности, образованной алгоритмом, отличается от предыдущей перестановки обменом местами двух соседних элементов. Эквивалентно, этот алгоритм находит гамильтонов цикл в перестановочном многограннике .
Этот метод был известен уже к 17-тому столетию как английское (колоколов), и Седжевие назвал его «возможно самым известным алгоритмом перечисления перестановок». Алгоритм можно реализовать таким образом, что время на создание каждой отдельной перестановки будет постоянным. Будучи простым и одновременно вычислительно эффективным, этот алгоритм имеет преимущество, что вычисления на перестановках, которые образует алгоритм, можно ускорить ввиду похожести соседних перестановок .
Алгоритм
Последовательность перестановок, образованных алгоритмом Джонсона — Троттера имеет естественную рекурсивную структуру, которая может быть образована рекурсивным алгоритмом. Однако реальный алгоритм Джонсона — Троттера не использует рекурсии и вместо неё вычисляет ту же последовательность перестановок с помощью простого итеративного метода. Дальнейшее улучшение алгоритма позволяет получать каждую перестановку за постоянное время.
Рекурсивная структура
Последовательность перестановок для заданного числа может быть образована из последовательности перестановок для путём размещения числа во все возможные позиции каждой из более коротких перестановок. Алгоритм Джонсона — Троттера следует следующей структуре: последовательность перестановок, которые он образует, состоит из блоков перестановок, так что внутри каждого блока перестановок сохраняется порядок чисел от 1 до и перестановки отличаются только положением числа . Сами блоки упорядочены рекурсивно согласно алгоритму Джонсона — Троттера для набора без одного элемента. Внутри каждого блока положения, в котором находится число , идут в убывающем или возрастающем порядке, меняя порядок с каждым следующим блоком. Позиции числа в первом блоке идут в убывающем порядке, во втором блоке в возрастающем порядке, в третьем блоке в убывающем и так далее .
Тогда для единственной перестановки одного элемента,
- 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
Продолжаем ту же процедуру для последующих значений , меняя убывающий и возрастающий порядок с каждой перестановкой. В последовательности перестановок в этой рекурсивной структуре каждая перестановка отличается от предыдущей позицией или меняются два меньших числа, унаследованных от предыдущей последовательности более коротких перестановок. В любом случае перестановки отличаются лишь обменом местами двух соседних элементов. Если , первая и последняя перестановки в последовательности отличаются лишь двумя соседними элементами (в позициях и ), что можно доказать по индукции.
Эту последовательность можно получить с помощью рекурсивного алгоритма , который создаёт последовательность перестановок меньшего размера, а затем осуществляет все возможные вставки наибольшего числа в созданную рекурсивно последовательность . Тот же самый порядок перестановок может быть описан как порядок, образованный следующим жадным алгоритмом . Начинаем с тождественной перестановки . Теперь последовательно переставляем наибольший элемент с левым или правым элементом так, что на каждом шаге образуется новая перестановка, которая не встречалась в списке перестановок до этого. Например, в случае последовательность начинается с , затем переставляется с левым соседом что приводит к . В этом месте перестановка с правым соседом приведёт к начальной перестановке , так что снова переставим с левым соседом и получаем , и так далее. Направление обмена позиций (слева или справа) в алгоритме всегда определяется однозначно. Однако действительный алгоритм Джонсона — Троттера не использует рекурсию и не требует хранения списка созданных перестановок. Вместо этого алгоритм вычисляет ту же последовательность перестановок простым итеративным методом .
Исходная версия
Как описывал Джонсон , алгоритм создания следующей перестановки из заданной перестановки осуществляется посредством следующих шагов.
- Для любого от 1 до пусть будет позицией, в которой значение помещается в перестановке . Если порядок чисел от 1 до в перестановке определяет чётную перестановку , пусть , в противном случает пусть .
- Находим наибольшее число , для которого определяет верное положение в перестановке , которая содержит число, меньшее . Меняем местами значения в позициях и .
Если нет числа , удовлетворяющего условиям второго шага алгоритма, алгоритм достиг финальной перестановки и прекращает работы. Эту процедуру можно реализовать со временем на перестановку.
Троттер дал альтернативную реализацию итеративного алгоритма для той же последовательности с комментариями в стиле ALGOL 60 .
Поскольку метод создаёт перестановки с чередованием чётных и нечётных, его легко модифицировать для создания только чётных перестановок или только нечётных перестановок — чтобы образовать следующую перестановку той же чётности просто выполняется та же процедура дважды .
Ускорение алгоритма Ивеном
Улучшение алгоритма Шимоном Ивеном даёт улучшение времени выполнения путём запоминания дополнительной информации для каждого элемента в перестановке – его позицию и направление (положительное, отрицательное или нулевое), в котором элемент движется (по существу, это та же информация, которая вычисляется с помощью чётности перестановки в версии алгоритма Джонсона). Начально направление числа 1 равно нулю, а все остальные элементы имеют отрицательные направления:
- 1 −2 −3
На каждом шаге алгоритм находит наибольший элемент с ненулевым направлением и переставляет его в указанном направлении:
- 1 −3 −2
Если это приводит к тому, что выбранный элемент оказывается в первой или последней позиции внутри перестановки, или если следующий элемент в том же направлении больше выбранного элемента, направление выбранного элемента сбарсывается в ноль:
- 3 1 −2
После каждого шага все элементы, большие выбранного элемента (имевшего нулевое направление), имеют направления, указывающие направление движения к выбранному элементу. То есть, направление положительно для элементов между началом перестановки и выбранным элементом и отрицательно для элементов от выбранного элемента до конца. Таким образом, в данном примере, после сдвига числа 2, число 3 помечается положительным направлением:
- +3 2 1
Оставшиеся два шага алгоритма для :
- 2 +3 1
- 2 1 3
Когда все числа остаются без пометок, алгоритм завершает работу.
Этот алгоритм работает за время на каждом шаге, в котором наибольшее число для обмена равно . Таким образом, обмен позиций, вовлекающих число , занимает постоянное время. since these swaps account for all but a 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 .
Более сложная версия алгоритма той же самой процедуры позволяет выполнять её за постоянное время на перестановку, но в этой модификации нужно исключить циклы из процедуры, что делает процедуру на практике медленнее .
Связанные структуры
Перестановочный многогранник
Множество всех перестановок элементов можно представить геометрически как перестановочный многогранник , то есть многогранник , образованный из выпуклой оболочки векторов, представляющих перестановки вектора . Хотя многогранник таким образом определяется в -мерном пространстве, на самом деле он является -мерным многогранником. Например, перестановочный многогранник четырёх элементов является трёхмерным многогранником, а именно, усечённым октаэдром . Если пометить каждую вершину перестановочного многогранника обратной перестановкой к перестановке, определённой координатами вершины, получающаяся разметка описывает граф Кэли симметрической группы перестановок элементов, поскольку образуется перестановками, в которых переставляются соседние пары элементов. Тогда любые две последовательные перестановки, образованные алгоритмом Джонсона — Троттера соответствуют в этом пути двум конечным вершинам ребра в перестановочном многограннике, а вся последовательность перестановок описывает гамильтонов путь в перестановочном многограннике, путь, проходящий через все вершины ровно один раз. Если последовательность перестановок дополнить ещё одним ребром, соединяющим последнюю перестановку с первой, в результате получим гамильтонов цикл .
Коды Грея
Код Грея для чисел с заданным основанием — это последовательность, которая содержит каждое число до указанного предела ровно один раз, и в этой последовательности каждая пара последовательных чисел отличаются одной цифрой. перестановок чисел от 1 до могут быть расположены в соответствии один-к-одному с числами от 0 до путём связывания каждой перестановки с последовательностью чисел , которые соответствуют числу позиций в перестановке, находящихся справа от значения и содержащих значение, меньшее (то есть, число инверсий для каждого ), затем эти последовательности как числа в * , то есть в с последовательностью оснований . Например, перестановка даст значения , , , и . Последовательность этих значений задаёт число
Исследователи комбинаторных алгоритмов определяют код Грея для набора комбинаторных объектов как упорядочение объектов, в котором каждые два последовательных объекта отличаются минимально возможным образом. В этом обобщённом смысле алгоритм Джонсона — Троттера образует код Грея для самих перестановок.
История
Алгоритм назван именами Селмера М. Джонсона и Хейла Ф. Троттера. Джонсон и Троттер создали алгоритм независимо друг от друга в начале 1960-х годов
Вне математики тот же метод был известен давно для церковных колоколов —он даёт процедуру, по которой набор колоколов могут звонить, проходя через все возможные перестановки, изменяя порядок только двух колоколов на одну перестановку. Эти так называемые «простые изменения» упоминались ещё в 1621 году для четырёх колоколов, а книга 1677 года приводит решение для шести колоколов. В более современных требованиях запрещено использовать колокол в той же позиции для трёх последовательных перестановок. Это требование нарушает простые изменения, а потому разработаны другие стратегии, в которых переставляются несколько колоколов на каждом шаге .
См. также
- , другой метод перечисления всех перестановок
- Тасование Фишера — Йетса , метод создания случайных перестановок
Примечания
- ↑ .
- ↑ .
- ↑ , с. section 3.
- .
- .
- .
- ↑ .
- .
- .
- , с. section 11.
- .
- В английской версии статьи к названию алгоритма приплюсован Штейнгауз. Для обоснования этого упоминается задача из книги Штейнгауза «Сто задач» (задача №98). Однако в данной задаче не упоминаются перестановки вообще, задача не имеет никакого отношения к алгоритму. Речь в задаче не идёт о построении перестановок, не говоря уже о построении всех перестановок. Выглядит так, что Штейнгауз притянут к статье за уши…
- .
Литература
- Nachum Dershowitz. A simplified loop-free algorithm for generating permutations // Nordisk Tidskr. Informationsbehandling (BIT). — 1975. — Т. 15 , вып. 2 . — С. 158–164 . — doi : .
- Edsger W. Dijkstra . // Acta Informatica. — 1976. — Т. 6 , вып. 4 . — С. 357–359 . — doi : .
- Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations // Journal of the ACM. — 1973. — Т. 20 , вып. 3 . — С. 500–513 . — doi : .
- Shimon Even. . — Macmillan, 1973.
- Selmer M. Johnson. // Mathematics of Computation. — 1963. — Т. 17 , вып. 83 . — С. 282–285 . — doi : . — .
- Jan Karel Lenstra, Alexander Rinnooy Kan. A recursive approach to the implementation of enumerative methods // (англ.) . — 1979. ; см. Section 2.1, "A minimum-change generator", pp. 3–8
-
Donald Knuth
.
Section 7.2.1.2: Generating All Permutations
// The Art of Computer Programming, volume 4A: Combinatorial Algorithms, Part 1. — 2011.
- Кнут Д. Э. Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 / под ред. И. В. Красикова.. — 1. — Москва: Вильямс, 2013. — Т. 4. — 960 с. — ISBN 978-5-8459-1744-7 .
- Gary McGuire. Bells, motels and permutation groups. — 2003.
- Carla Savage. A survey of combinatorial Gray codes // . — 1997. — Т. 39 , вып. 4 . — С. 605–629 . — doi : . — . — .
- Robert Sedgewick. // ACM Comput. Surv.. — 1977. — Т. 9 , вып. 2 . — С. 137–164 . — doi : .
- Trotter H. F. Algorithm 115: Perm // Communications of the ACM. — 1962. — Август ( т. 5 , вып. 8 ). — С. 434–435 . — doi : .
- Williams, Aaron. The Greedy Gray Code Algorithm // Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings / Frank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack. — Springer, 2013. — Т. 8037. — С. 525–536. — (Lecture Notes in Computer Science). — doi : .
![](https://cdn.wafarin.com/avatars/38e18925d2a8e9c1df99bd4d6462af86.jpg)
- 2020-09-29
- 1