슈타인하우스-존슨-트로터 알고리즘

슈타인하우스-존슨-트로터 알고리즘 또는 플레인 체인지라고도 불리는 존슨-트로터 알고리즘은 휴고 스타인하우스, 셀머 M. 존슨, 헤일 F의 이름을 딴 알고리즘이다. $n{\displaystyle }$ ${\displaystylen}$ 요소의$$ 모든 순열을 생성하는 트로터.생성되는 시퀀스의 각 순열은 시퀀스의 인접한 두 요소를 스와핑하여 이전 순열과 다르다.동등하게, 이 알고리즘은 전유체에서 해밀턴 사이클을 찾는다.

이 방법은 이미 17세기 영국 변경 링거들에게 알려져 있었으며, Sedgewick(1977)은 이 방법을 "아마도 가장 두드러진 순열 알고리즘"이라고 부른다.알고리즘 버전은 순열당 평균 시간이 일정하게 구현될 수 있다.단순하고 계산적으로 효율적일 뿐만 아니라, 이 알고리즘은 생성되는 연속 순열 사이의 유사성 때문에 생성되는 순열에 대한 후속 연산을 가속화할 수 있다는 장점을 가지고 있다.^[1]

알고리즘.

슈타인하우스에 의해 생성된 순열의 순서-존슨-트로터 알고리즘은 자연 재귀 구조를 가지고 있으며, 재귀 알고리즘에 의해 생성될 수 있다.하지만 실제 스타인하우스는-Johnson-Trotter 알고리즘은 반복을 사용하지 않고, 대신 단순한 반복 방법으로 같은 순열의 순열을 계산한다.나중에 개선하면 순열당 일정한 평균 시간으로 실행할 수 있다.

재귀구조

$주어진{\displaystyle }$ 숫자 $n{\displaystyle }$ ${\displaystyle n}$의 순열 순서는 n -${\displaystyle }$1 ${\displaystyle$ n-1$}$의 순열 순열 순서에서 n ${\displaystyle n}$을(를) 각각의 짧은 순열에서 가능한 위치에$$ 배치하여$$ 구성할 수 있다$$.슈타인하우스-존슨-트로터 알고리즘은 이 구조를 따른다$:{\displaystyle }$ 이 알고리즘이 생성하는 순열의 ${\displaystyle \mathrm{순열}}$은${\displaystyle }$( n${\displaystyle }$-${\displaystyle }$1 )$$! {\$displaystyle (n-1)!}$개의 순열 블록으로$$ 구성된다. 따라서 각 블록 내에서 순열은 $1$부터${\displaystyle }$n - ${\displaystyle 1}$까지 숫자의 순서에 동의하고$$ $n{\displaystyle }$ ${\displaysty$ $n-1}$의 위치에서만 차이가 난다.$닐$ 앤$\}$스타인하우스에 따르면, 블록 자체는 재귀적으로 주문된다.Johnson-Trotter 알고리즘을 통해 한 가지 더 적은 요소.각 블록 내에서 $n{\displaystyle }$ ${\displaystylen}$이(가) 배치되는$$ 위치는 내림차순 또는 오름차순으로 발생하며, 블록은 첫 번째 블록에서$$ $n{\displaystyle }$ ${\displaystylen}$의 위치가 내림차순으로, 두 번째 블록에서는 오름차순으로, 세 번째 블록에서는 d에 위치한다.경솔한 명령 ^[2]등

따라서, 한 요소에 대한 단일 순열에서,

1

하나는 가능한 각 위치에 숫자 2를 내림차순으로 배치하여 두 요소에 두 개의 순열 목록을 구성할 수 있다.

1 2

2 1

그런 다음, 첫 번째 순열 1 2를 내림차순으로, 그리고 순열 2 1을 오름차순으로 세 개의 순열 각각에 숫자 3을 배치할 수 있다.

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

$n{\displaystyle }$ ${\displaystylen$의 내림차순과 오름차순을 교대로 하는 동일한 배치 패턴은 $n{\displaystyle }$ ${\displaystylen}$의 더 큰 값에 적용된다$.$ 이 재귀적 구조의 순열 순서에서 $각{\displaystyle }$ 순열은 n ${\displa$}의 한 번에 한 위치 이동에 의해 이전의 순열과 다르다.$ystyle n$ 또는 이전 순서의 짧은 순열에서 상속된 두 개의 작은 숫자의 변경.어느 경우든 이 차이는 단지 인접한 두 원소의 전치일 뿐이다.> ${\displaystyle n>1$}이$($가) 있을 때, 또한 유도에 의해 증명될 수 있는 것처럼, 순서의 첫 번째 요소와 최종 요소도 인접한 두 요소(숫자 1과 2의 위치)에서만 차이가 난다.

이 시퀀스는 더 작은 순열의 순서를 구성하고 가장 큰 숫자의 가능한 모든 삽입을 재귀적으로 생성된 시퀀스에 수행하는 재귀 알고리즘에 의해 생성될 수 있다.같은 순열의 순서는 다음과 같은 탐욕 알고리즘에 의해 생성된 순서와 동등하게 설명될 수 있다.^[3]ID 순열 $1{\displaystyle \mathrm{}}$ ${\displaystyle 2}$…$[\displaystyle$ 1$\;2\;\ldots \;n$ 이제 반복적으로 가능한 최대 항목과 왼쪽 또는 오른쪽으로의 항목을 바꾸어 각 단계에서 이전에는 순열 목록에서 접하지 못했던 새로운 순열이 생성된다.예를 들어, 사례 $n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$에서 시퀀스는$$ 123으로 시작한 다음 왼쪽 인접 항목과 함께 3을 건너뛰어 132를 얻는다.이때부터 오른쪽 이웃 2로 3을 뒤집으면 초기 순열 123이 나오므로 대신 왼쪽 이웃 1로 3을 뒤집고 312 등에 도착한다.전이 방향(왼쪽 또는 오른쪽)은 항상 이 알고리즘에서 고유하게 결정된다.하지만 실제 스타인하우스는-존슨-트로터 알고리즘은 재귀법을 사용하지 않으며, 이미 마주친 순열을 추적할 필요가 없다.대신에, 그것은 간단한 반복적인 방법으로 같은 순열의 순서를 계산한다.

원본

$존슨$(1963년$)$이 설명한 대로 주어진 순열에서 다음 $순열$을 생성하기 위한 $알고리즘$은 다음 단계를 수행한다$.$

• 1에서$n$까지 각 $i{\displaystyle }$ ${\$$displaystyle$ $i$$}$에 대해$$$x{\displaystyle }$ ${\displaystyle i_{}}$ ${\$$displaystyle$ $x_$${i}$ 값을 순열 $perm{\displaystyle }$ ${\displaystyle$ $\$$pi$}에$$ 배치하도록$$ 두십시오$.$ 숫자 $순서$가 $1$인 경우$display$ {\$displaystyle$$$\$pi$}$$ 짝수 순열을 정의한다. $그렇지{\displaystyle {}_{}}$ 않으면$$ $y{\displaystyle {}_{}}$${\displaystyle {}_{}}$= ${\displaystyle \mathrm{x}}$ ${\displaystyle {}_{}}$- 1 ${\displaystyle y_{i}=x_{i$}-1$, y$${\displaystyle {}_{}}$= ${\displaystyle \mathrm{x}}$ ${\displaystyle {}_{}}$+ 1 ${\displaystyle y_{i}=x_{i}+1$
• $y{\displaystyle }$ ${\$이(가) i ${\displaystyle i}$보다 작은 숫자를 포함하는$$ 순열 $\pi {\displaystyle }$ ${\displaystyle \pi }$에서 유효한 위치를 정의하는$$ 가장$$ 큰 $숫자{\displaystyle }$ i ${\$ $y_{i$$}$$$및$$ ${\displaystyle {yi}_{}}\}$에서 값을 $교환$하십시오.

알고리즘의 두 번째 단계의 조건을 만족하는 숫자 $i{\displaystyle }$ ${\displaystyle$ i$}$을(를$$) 찾을 수 없을 때 알고리즘은 시퀀스의 최종 순열에 도달하고 종료된다.이 절차는 순열당 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle O(n)}$번으로$$ 구현될 수 있다.

트로터(1962)는 동일한 시퀀스에 대해 ALGOL 60 표기법으로 반복 알고리즘의 대체 구현을 제공한다.

이 방법은 짝수 및 홀수 사이에서 교대로 순열을 생성하기 때문에 짝수 순열만 생성하거나 홀수 순열만 생성하도록 쉽게 수정할 수 있다: 주어진 순열에서 동일한 패리티의 다음 순열을 생성하려면 동일한 절차를 두 번 적용하십시오.^[4]

이븐스 스피드 업

시몬 이븐에 의한 후속 개선은 그 위치, 그리고 현재 움직이고 있는 방향(양, 음 또는 0)의 각 요소에 대한 추가 정보를 순열화(permution)에 저장함으로써 알고리즘의 실행시간을 향상시킨다(본질적으로 이것은 퍼머타티오의 패리티를 이용하여 계산한 것과 동일한 정보다).n Johnson의 알고리즘 버전에서).처음에 숫자 1의 방향은 0이며, 다른 모든 원소는 음의 방향을 가진다.

1 −2 −3

각 단계에서 알고리즘은 0이 아닌 방향으로 가장 큰 원소를 찾아 지정된 방향으로 교환한다.

1 −3 −2

이로 인해 선택한 원소가 순열 내에서 첫 번째 또는 마지막 위치에 도달하거나 같은 방향의 다음 원소가 선택한 원소보다 크면 선택한 원소의 방향은 0으로 설정된다.

3 1 −2

각 단계 후 선택한 요소(이전에는 방향 0을 가졌던)보다 큰 모든 요소에는 선택된 요소를 향한 움직임을 나타내도록 방향이 설정된다.즉, 순열의 시작과 선택한 원소 사이의 모든 원소에 대해 양이고, 끝을 향한 원소에 대해서는 음이다.따라서 이 예에서 숫자 2가 이동한 후 숫자 3은 다시 방향을 표시하게 된다.

+3 2 1

$n{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle n=3}$ 알고리즘의 나머지 두 단계는 다음과$$ 같다.

2 +3 1

2 1 3

모든 숫자가 표시되지 않으면 알고리즘은 종료된다.

이 알고리즘은 이동해야 할 최대 숫자가 n-+ 1인모든 단계에 대해 O(나는){O(나는)\displaystyle}시간이 걸린다.따라서 숫자 $n{\displaystyle }$ ${\$$displaystyle$ $n$$}$을(를$)$ 포함하는 스왑은 일정한 시간만 소요된다$.$ 이러한 스왑은 알고리즘에 의해 수행되는 모든 스왑의 $n$을 제외한 모든 부분을$$ 차지하기 때문에, 적은 수의 순열이 더 큰 아모를 사용함에도 불구하고 생성된 순열당 평균 시간도 일정하다.때아닌^[1]

동일한 절차의 더 복잡한 반복되지 않는 버전은 모든 경우에 순열당 일정한 시간 동안 수행될 수 있도록 허용하지만, 절차에서 루프를 제거하는 데 필요한 수정은 실행 속도를 더디게 만든다.^[5]

관련 구조물

순면체

n개 항목의 모든 순열 세트는 n! 벡터의 볼록한 선체에서 형성된 폴리토프인 순열체로 기하학적으로 표현될 수 있다(1,2,...n).n차원 공간에서 이런 식으로 정의되기는 하지만, 실제로는 (n - 1)차원 다면체인데, 예를 들어, 네 가지 항목의 유무체는 잘린 팔면체인 3차원 다면체다.만약 정점 좌표에 의해 정의된 순열의 역 순열에 의해 순열의 각 정점에 라벨이 붙는 경우, 결과 라벨링은 인접한 항목 쌍을 교환하는 순열에 의해 생성된 n개 항목의 순열의 대칭 그룹에 대한 Cayley 그래프를 설명한다.따라서 스타인하우스에 의해 생성된 순서에서 각각 2회 연속 순열.존슨-트로터 알고리즘은 이러한 방식으로 순면체에서 가장자리의 끝점을 형성하는 두 정점에 대응하며, 순열의 전체 순서는 순면체에서 해밀턴 경로를 설명하는데, 이는 각 정점을 정확히 한 번 통과하는 경로다.마지막 순열에서 첫 순열까지 에지를 한 개 더 추가해 순열 순서가 완성되면 그 결과는 대신 해밀턴 사이클이다.^[6]

그레이 코드

주어진 라디스에서 숫자에 대한 회색 코드는 연속된 숫자의 각 쌍이 한 자릿수에서 1씩 차이 나도록 주어진 한계까지 정확히 한 번 각 숫자를 포함하는 시퀀스다.1에서 n까지의 n! 순열은 0에서 n! - 1까지의 n! 순열과 각 순열과 값 i의 오른쪽에 있는 순열의 위치 수를 카운트하고 (즉_i, 역순의 수)보다 작은 값을 포함하는 숫자 c의 순열로 짝을 지어 일대일 대응으로 배치될 수 있다.r은 2개의 반전 값 중 더 큰 값)이며, 그 다음 이 시퀀스를 요인 번호 시스템의 숫자로 해석한다. 즉, radix 시퀀스가 있는 혼합 radix 시스템(1,2,3,4,...).예를 들어, 순열(3,1,4,5,2)은₁ c = 0, c₂ = 0, c₃ = 2, c₄ = 1, c₅ = 1 값을 제공한다.이러한 값의 순서(0,0,2,1,1)는 숫자를 제공한다.

0 × 0! + 0 × 1! + 2 × 2! + 1 × 3! + 1 × 4! = 34.

슈타인하우스에 의해 생성된 시퀀스의 연속 순열Johnson-Trotter 알고리즘은 1개씩 다른 반전 수를 가지며, 요인 번호 시스템의 회색 코드를 형성한다.^[7]

보다 일반적으로 조합 알고리즘 연구자들은 조합 개체 집합에 대한 회색 코드를 정의하여 연속적인 두 개 개체 각각이 가능한 최소한의 방식으로 서로 다른 개체의 순서를 정했다.이런 일반화된 의미에서 스타인하우스는-존슨-트로터 알고리즘은 순열 자체에서 회색 코드를 생성한다.

역사

이 알고리즘은 휴고 스타인하우스, 셀머 M. 존슨, 헤일 F의 이름을 따서 지어졌다. 트로터.존슨과 트로터는 1960년대 초에 서로 독립적으로 알고리즘을 발견했다.1958년에 처음 출판되어 1963년에 영어로 번역된 슈타인하우스의 책은 한 입자가 다른 입자를 압도할 때 각각 선을 따라 일정한 속도로 움직이고 위치를 교환하는 입자 시스템에 의해 모든 순열을 발생시키는 관련 퍼즐을 묘사하고 있다.n > 3은 스와프 횟수가 순열 수보다 훨씬 적기 때문에 해결이 불가능하지만, 스타인하우스는–존슨-트로터 알고리즘은 모든 순열을 생성하는 일정하지 않은 속도를 가진 입자의 움직임을 설명한다.

수학 외에, 같은 방법은 교회 종을 울리는 변화법으로서 훨씬 더 오랫동안 알려져 있었다: 그것은 종을 한 세트가 가능한 모든 순열을 통해 울릴 수 있는 절차를 주고, 변화당 두 개의 종만 순서를 바꾼다.소위 "플레인 변화"라고 불리는 이 책들은 4개의 종에 대해 1621년에 기록되었고, 파비안 스테드먼의 1677년 책에는 6개의 종에 대한 해결책이 나열되어 있다.보다 최근에, 변경 링거들은 세 번의 연속 순열 동안 어떤 종도 같은 위치에 머물 수 없다는 규칙을 지켜왔다; 이 규칙은 평범한 변경에 의해 위반되기 때문에 변경당 여러 종을 교환하는 다른 전략을 고안했다.^[8]

참고 항목

• 힙 알고리즘
• 피셔-예이츠 셔플

메모들

참조