Штейнгауз-Джонсон-Троттер алгоритм или алгоритм Джонсон-Trotter , называемые также простые изменения , является алгоритмом имени Штейнгауза , Зельмер М. Джонсона и Hale Ф. Trotter , который генерирует все перестановки из п элементов. Каждая перестановка в генерируемой ею последовательности отличается от предыдущей перестановкой местами двух соседних элементов последовательности. Эквивалентно этот алгоритм находит гамильтонов цикл в пермутоэдре .
Этот метод был известен уже в 17 веке английским специалистам по вызову изменений , и Седжвик (1977) назвал его «возможно, наиболее известным алгоритмом перестановочного перечисления». Помимо простоты и вычислительной эффективности, он имеет то преимущество, что последующие вычисления генерируемых им перестановок могут быть ускорены, поскольку эти перестановки очень похожи друг на друга. [1]
Рекурсивная структура
Последовательность перестановок для данного числа n может быть сформирована из последовательности перестановок для n - 1, помещая число n в каждую возможную позицию в каждой из более коротких перестановок. Когда перестановка n - 1 элементов является четной перестановкой (как это верно для первой, третьей и т. Д. Перестановок в последовательности), то число n размещается во всех возможных позициях в порядке убывания, от n до 1; когда перестановка n - 1 элементов нечетная, номер n размещается во всех возможных позициях в порядке возрастания. [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 и т. Д. Тот же шаблон размещения, чередующийся между размещениями по убыванию и возрастанию. of n применяется для любого большего значения n . Таким образом, каждая перестановка отличается от предыдущей либо перемещением n по одной позиции за раз , либо изменением двух меньших чисел, унаследованных от предыдущей последовательности более коротких перестановок. В любом случае это различие - просто перестановка двух соседних элементов. При n > 1 первый и последний элементы последовательности также различаются только двумя соседними элементами (положениями чисел 1 и 2), что можно показать по индукции.
Хотя эта последовательность может быть сгенерирована рекурсивным алгоритмом, который создает последовательность меньших перестановок, а затем выполняет все возможные вставки наибольшего числа в рекурсивно сгенерированную последовательность, фактический алгоритм Штейнхауса – Джонсона – Троттера избегает рекурсии, вместо этого вычисляя ту же последовательность перестановок итерационным методом.
Существует эквивалентное и концептуально несколько более простое определение порядка перестановок Штейнгауза-Джонсона-Троттера с помощью следующего жадного алгоритма: [3] Начнем с тождественной перестановки. Теперь мы многократно транспонируем максимально возможную запись с записью влево или вправо, так что на каждом шаге создается новая перестановка, которая ранее не встречалась в списке перестановок. Например, в случае мы начинаем с 123, затем мы переворачиваем 3 с его левым соседом и получаем 132. Затем мы переворачиваем 3 с его левым соседом 1, так как отражение 3 с его правым соседом 2 снова даст 123, что мы видели раньше, поэтому мы приходим к 312 и т. Д. В этом алгоритме всегда однозначно определяется направление транспозиции (влево или вправо).
Алгоритм
Как описано Джонсоном (1963) , алгоритм генерации следующей перестановки из данной перестановки π выполняет следующие шаги
- Для каждого i от 1 до n пусть x i будет позицией, в которой значение i помещается в перестановку π. Если порядок чисел от 1 до i - 1 в перестановке π определяет четную перестановку , пусть y i = x i - 1; в противном случае пусть y i = x i + 1.
- Найдите наибольшее число i, для которого y i определяет допустимую позицию в перестановке π, которая содержит число меньше i . Поменяйте местами значения в позициях x i и y i .
Когда не может быть найдено ни одного числа i , удовлетворяющего условиям второго шага алгоритма, алгоритм достиг последней перестановки последовательности и завершается. Эта процедура может быть реализована за O ( n ) раз на перестановку.
Троттер (1962) дает альтернативную реализацию итерационного алгоритма для той же последовательности в слегка комментированной нотации АЛГОЛА 60 .
Поскольку этот метод генерирует перестановки, которые чередуются между четными и нечетными, его можно легко изменить для генерации только четных перестановок или только нечетных перестановок: чтобы сгенерировать следующую перестановку той же четности из данной перестановки, просто примените ту же процедуру дважды . [4]
Даже ускорение
Последующее усовершенствование Shimon Even обеспечивает улучшение времени работы алгоритма за счет сохранения дополнительной информации для каждого элемента в перестановке: его позиции и направления (положительного, отрицательного или нулевого), в котором он движется в данный момент (по сути, это та же самая информация, вычисленная с использованием четности перестановки в версии алгоритма Джонсона). Изначально направление числа 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, всех свопов, выполняемых алгоритмом, среднее время на одну сгенерированную перестановку также является постоянным, даже несмотря на то, что небольшое количество перестановок потребует большего количества времени. [1]
Более сложная версия той же процедуры без зацикливания позволяет выполнять ее за постоянное время для каждой перестановки в каждом случае; однако модификации, необходимые для исключения петель из процедуры, на практике делают ее медленнее. [5]
Геометрическая интерпретация
Множество всех перестановок из п элементов может быть представлено геометрический с помощью перестановочного многогранника , то многогранник формируется из выпуклой оболочки из п ! векторы, перестановки вектора (1,2, ... n ). Хотя он определен таким образом в n -мерном пространстве, на самом деле это ( n - 1) -мерный многогранник; например, пермутоэдр на четырех элементах представляет собой трехмерный многогранник, усеченный октаэдр . Если каждая вершина перестановочный многогранник помечена обратной перестановки к перестановке , определяемой своими координатами вершин, в результате маркировки описывает граф Кэли из симметрической группы перестановок на п элементов, а порожденный перестановок , которые своп смежных пар элементов. Таким образом, каждые две последовательные перестановки в последовательности, генерируемой алгоритмом Штейнхауса – Джонсона – Троттера, соответствуют двум вершинам, которые образуют конечные точки ребра в пермутоэдре, а вся последовательность перестановок описывает гамильтонов путь в пермутоэдре, путь, который проходит через каждую вершину ровно один раз. Если последовательность перестановок завершается добавлением еще одного ребра из последней перестановки к первому в последовательности, результатом вместо этого является гамильтонов цикл. [6]
Связь с кодами Грея
Код Грея для чисел в данной системе счисления представляет собой последовательность , которая содержит каждое число до заданного предела ровно один раз, таким образом , что каждая пара последовательных чисел отличаются один в одной цифре. П ! перестановки n чисел от 1 до n могут быть помещены во взаимно однозначное соответствие с n ! числа от 0 до n ! - 1 путем объединения каждой перестановки в пару с последовательностью чисел c i, которые подсчитывают количество позиций в перестановке, которые находятся справа от значения i и содержат значение меньше, чем i (то есть количество инверсий, для которых i равно большее из двух инвертированных значений), а затем интерпретировать эти последовательности как числа в факторной системе счисления , то есть в смешанной системе счисления с основанием счисления (1,2,3,4, ...). Например, перестановка (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 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.
Последовательные перестановки в последовательности, генерируемой алгоритмом Штейнхауса – Джонсона – Троттера, имеют номера инверсий, которые отличаются на единицу, образуя код Грея для факторной системы счисления. [7]
В более общем плане исследователи комбинаторных алгоритмов определили код Грея для набора комбинаторных объектов как упорядочение объектов, в котором каждые два последовательных объекта отличаются минимально возможным образом. В этом обобщенном смысле алгоритм Штейнхауса – Джонсона – Троттера генерирует код Грея для самих перестановок.
История
Алгоритм назван в честь Хьюго Штайнхауса , Селмера М. Джонсона и Хейла Ф. Троттера . Джонсон и Троттер открыли алгоритм независимо друг от друга в начале 1960-х годов. Книга Штейнхауса, первоначально опубликованная в 1958 году и переведенная на английский язык в 1963 году, описывает связанную загадку генерации всех перестановок системой частиц, каждая из которых движется с постоянной скоростью по линии и меняет позиции, когда одна частица догоняет другую. Никакое решение невозможно для n > 3, потому что количество перестановок намного меньше, чем количество перестановок, но алгоритм Штейнхауса – Джонсона – Троттера описывает движение частиц с непостоянными скоростями, которые генерируют все перестановки.
Вне математики тот же метод был известен гораздо дольше как метод изменения звонка церковных колоколов: он дает процедуру, с помощью которой набор колоколов может быть перебран через все возможные перестановки, изменяя порядок только двух колоколов за изменение. Эти так называемые «простые изменения» были записаны еще в 1621 году для четырех колоколов, а в книге Фабиана Стедмана 1677 года перечислены решения для шести колоколов. В последнее время меняющие звоны соблюдают правило, согласно которому ни один звонок не может оставаться в одном и том же положении в течение трех последовательных перестановок; это правило нарушается простыми изменениями, поэтому были разработаны другие стратегии, которые меняют местами несколько колокольчиков за изменение. [8]
Смотрите также
- Алгоритм кучи
- Фишер – Йетс в случайном порядке
Заметки
- ^ а б Седжвик (1977) .
- Перейти ↑ Savage (1997) , раздел 3.
- ^ Уильямс, Аарон (2013). «Алгоритм жадного кода Грея». Материалы 13-го Международного симпозиума по алгоритмам и структурам данных (WADS) . Лондон (Онтарио, Канада). С. 525–536. DOI : 10.1007 / 978-3-642-40104-6_46 .
- ^ Кнут (2011) .
- ^ Эрлих (1973) ; Дершовиц (1975) ; Седжвик (1977) .
- ^ См., Например, раздел 11 Savage (1997) .
- ^ Дейкстра (1976) ; Кнут (2011) .
- ^ Макгуайр (2003) ; Кнут (2011) .
Рекомендации
- Дершовиц, Нахум (1975), «Упрощенный алгоритм без циклов для генерации перестановок», Nordisk Tidskr. Informationsbehandling (БИТ) , 15 (2): 158-164, DOI : 10.1007 / bf01932689 , МР 0502206.
- Дейкстра, Эдсгер В. (1976), «На перчатке, брошенной Дэвидом Грайсом» (PDF) , Acta Informatica , 6 (4): 357–359, doi : 10.1007 / BF00268136 , MR 0426492. Хотя Дийкстра не цитирует никакой предшествующей литературы, более ранний проект EWD502 показывает, что он знал о Троттере (1962) .
- Эрлиха, Гедеон (1973), "Loopless алгоритмы для генерации перестановок, комбинации и другие комбинаторные конфигурации", Журнал ACM , 20 (3): 500-513, DOI : 10,1145 / 321765,321781.
- Эвен, Шимон (1973), Алгоритмическая комбинаторика , Макмиллан.
- Джонсон, Сельмер М. (1963), "Генерация перестановок соседних транспозиций", Математика вычислений , 17 : 282-285, DOI : 10,1090 / S0025-5718-1963-0159764-2 , JSTOR 2003846 , МР 0159764.
- Кнут, Дональд (2011), «Раздел 7.2.1.2: Создание всех перестановок» , Искусство компьютерного программирования , том 4A.
- Макгуайр, Гэри (2003), Bells, мотели и группы перестановок , CiteSeerX 10.1.1.6.5544.
- Savage, Карла (1997), "Исследование комбинаторных кодов Грея", SIAM Обзор , 39 (4): 605-629, CiteSeerX 10.1.1.39.1924 , DOI : 10,1137 / S0036144595295272 , JSTOR 2132693 , МР 1491049.
- Седжвик, Роберт (1977), "Методы генерации перестановок", ACM Comput. Surv. , 9 (2): 137-164, DOI : 10,1145 / 356689,356692.
- Steinhaus, Hugo (1964), Сто задач элементарной математики , New York: Basic Books, стр. 49–50, MR 0157881.
- Trotter, HF (август 1962 г.), "Алгоритм 115: Пермь", коммуникаций ACM , 5 (8): 434-435, DOI : 10,1145 / 368637,368660.