힙 알고리즘

A(암버), B(파란), C(사이언) 및 D(검은 빨강) 네 글자를 허용하는 힙의 알고리즘에 사용된 24개의 순열과 23개의 스왑의 지도

힙의 알고리즘에 의해 생성된$$ $길이{\displaystyle }$n = ${\displaystyle 4}$ ${\displaystyle$ n$=4$}의 모든 순열의 휠 다이어그램. 여기서 각 순열은 컬러 코딩(1=파란색, 2=녹색, 3=노란색, 4=빨간색)이다.

힙의 알고리즘은 n개 객체의 가능한 모든 순열을 생성한다.1963년 B. R. 힙이 처음 제안한 것이다.^[1]알고리즘은 움직임을 최소화한다. 알고리즘은 한 쌍의 원소를 상호 교환하여 이전 원소로부터 각각의 순열을 생성한다. 다른 n-2 원소는 방해받지 않는다.1977년 순열 생성 알고리즘에 대한 검토에서 로버트 세지윅은 그것이 당시 컴퓨터에 의한 순열 생성에 가장 효과적인 알고리즘이라고 결론지었다.^[2]

힙의 알고리즘에 의해 생성된 n개의 객체의 순열 순서는 n+1 객체의 순열 순열의 시작이다.따라서 힙의 알고리즘(OEIS의 시퀀스 A280318)에 의해 생성되는 무한 순열의 한 가지가 있다.

알고리즘 세부 정보

$서로{\displaystyle }$ 다른 요소가 n개 들어$$$$있지 않은$컬렉션$ C {\$displaystyle$ C}에 대해 힙은 각 단계에서 이들 요소의 가능한 모든 순열을 정확히 한 번 생성하기 위해 전환할 요소 쌍을 선택하는 체계적인 방법을 찾았다.

감소 및 정복 방법으로 재귀적으로 설명되는 힙의 알고리즘은 컬렉션의 $k{\displaystyle }$ ${\displaystyle k}$ 초기$$ 요소의 각 단계에서 작동한다.초기 $k{\displaystyle }$= ${\displaystyle n}$ ${\displaystyle$ k$=n}$ < n ${\displaystyle k<n$ 각 단계마다 동일한 $n{\displaystyle }$- ${\displaystyle k}$ ${\displaystyle n-k}$ 최종$$ 요소로 끝나는 $k{\displaystyle }$! ${\displaystystyle$ k$!}$ 순열이$$ 생성된다.$이{\displaystyle }$ $작업$은 ${\displaystyle \text{초기}}$${\displaystyle \mathrm{k}}$ -$$1 {\$displaystyle$k{\$text{th$} 요소를 변경하지 않은 상태에서$$ 한 번 자체 호출한 다음 ${\displaystyle }$ k - 1 ${\$ 요소를$$ 교환한 후 $k{\displaystyle }$- ${\displaystyle 1}$ ${\$$displaystyle k-1}$ 요소를$$ 사용하여$$수행된다.재귀 호출은 초기 $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$ 요소를$$ 수정하며, 각 반복마다 규칙이 있어야 마지막 요소와 교환할 항목을 선택할 수 있다.힙의 방법은 이 단계에서 작동되는 요소 수의 패리티에 의해 선택될 수 있다고 말한다.$k{\displaystyle }$ ${\displaystyle k}$이(가) 짝수인 경우 최종 요소는 각 요소 지수와 반복적으로 교환된다.$k{\displaystyle }$ ${\displaystyle k}$이(가) 홀수인 경우 최종 요소는 항상 첫 번째 요소와 교환된다.

절차 발생시키다(k : 정수의, A : 배열하다 의 아무 것이나):     만일 k = 1 그때         생산량(A)     다른         // 변경되지 않은 k-th 순열 생성         // 초기 k = 길이(A)         발생시키다(k - 1, A)          // 각 k-1 초기값과 스와핑된 k번째 순열 생성         을 위해 i := 0; i < k-1; i += 1 하다             // k(짝수 또는 홀수)의 패리티에 따른 스왑 선택             만일 k 이다 짝수 그때                 바꾸다(A[i], A[k-1]) // 영점 조정, k-th는 k-1이다.             다른                 바꾸다(A[0], A[k-1])             종지부를 찍다 만일             발생시키다(k - 1, A)         종지부를 찍다 을 위해     종지부를 찍다 만일 

또한 알고리즘을 비반복 형식으로 작성할 수 있다.^[3]

절차 발생시키다(n : 정수의, A : 배열하다 의 아무 것이나):     // c는 스택 상태의 인코딩이다.c[k] 생성(k - 1, A)이 호출될 때 사용할 for-loop 카운터를 인코딩함     c : 배열하다 의 인트로      을 위해 i := 0; i < n; i += 1 하다         c[i] := 0     종지부를 찍다 을 위해      생산량(A)          // i는 스택 포인터와 유사하게 작동함     i := 0;     하는 동안에 i < n 하다         만일  c[i] < i 그때             만일 i 이다 짝수 그때                 바꾸다(A[0], A[i])             다른                 바꾸다(A[c[i]], A[i])             종지부를 찍다 만일             생산량(A)             // 포루프를 종료하는 동안 스왑이 발생함.루프용 카운터의 증가 시뮬레이션             c[i] += 1             // 어레이의 베이스 케이스 아날로그에 포인터를 가져와서 베이스 케이스에 도달하는 재귀 호출 시뮬레이션             i := 0         다른             // 호출 생성(i+1, A)은 포루프가 종료됨에 따라 종료되었다.상태를 재설정하고 포인터를 증가시켜 스택을 여는 시뮬레이션을 수행하십시오.             c[i] := 0             i += 1         종지부를 찍다 만일     종지부를 찍다 하는 동안에 

증명

이 증거에서는 아래 구현을 힙 알고리즘으로 사용할 것이다.최적화는 아니지만(아래 섹션 참조),^{[clarification needed]} 그럼에도 불구하고 구현은 정확하며 모든 순열이 생성될 것이다.아래의 구현을 이용하는 이유는 분석이 용이하고, 특정 패턴을 쉽게 설명할 수 있기 때문이다.

절차 발생시키다(k : 정수의, A : 배열하다 의 아무 것이나):     만일 k = 1 그때         생산량(A)     다른         을 위해 i := 0; i < k; i += 1 하다             발생시키다(k - 1, A)             만일 k 이다 짝수 그때                 바꾸다(A[i], A[k-1])             다른                 바꾸다(A[0], A[k-1])             종지부를 찍다 만일          종지부를 찍다 을 위해     종지부를 찍다 만일 

클레임: 어레이 A의 길이가 n인 경우, 힙의 알고리즘을 수행하면 A가 1만큼 오른쪽으로 "회전"(즉, 각 요소가 첫 번째 위치를 차지하는 마지막 요소로 오른쪽으로 이동)되거나, n이 짝수인지 홀수인지에 따라 A가 변경되지 않게 된다.

기준: 힙의 알고리즘은 단순히 A를 순서에 따라 변경되지 않고 반환하므로$$ 위의 $주장$은${\displaystyle }$n = ${\displaystyle 1}${\$displaystyle n=$1}에 대해 사소한 사실로 유지된다.

유도:일부 $i{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle i\geq$ 1$}$에 대한 클레임이 사실이라고 가정해 보십시오$.$ 그러면 $i{\displaystyle }$+ ${\displaystyle 1}${\$displaystyle i+$$1$}에 대해 두 가지 사례를 처리해야 할 $것$입니다$:$${\displaystyle }$i + ${\displaystyle 1}${\$displaystyle i+$1}는$$ 짝수 또는 홀수입니다.

A의 경우, $n{\displaystyle }$= ${\displaystyle \mathrm{i}}$+ ${\displaystyle 1}$ ${\displaystyle n=i+1$}이$$짝수인$$ 경우, 유도 가설에 의해 가정된 대로 서브 어레이에 힙 알고리즘을 수행한 후 첫 번째 i 요소의 하위 집합이 변경되지 않은 상태로 유지된다.서브 어레이에서 힙 알고리즘을 수행한 다음 스와핑 작업을 수행함으로써, $k{\displaystyle }$≤ ${\displaystyle \mathrm{i}}$+ ${\displaystyle 1}$ ${\displaystyle k\leq i+1}$이 있는 for-loop의 k번째 반복에서 A의 k번째 요소는 일종의 "버퍼"로 생각할 수 있는 A의 마지막 위치로 스왑될 것이다$.$첫 번째 요소와 마지막 요소를 교환한 다음 두 번째 요소와 마지막 요소를 교환할 때까지 계속 교환하면 어레이가 마침내 회전을 경험하게 된다.위의 내용을 설명하려면 ${\displaystyle \mathrm{아래}}$ 사례 $n{\displaystyle }$= 4 ${\displaystyle n=4}$을(를) 참조하십시오.

1,2,3,4 ...Original Array 1,2,3,4 ... 1st iteration (Permute subset) 4,2,3,1 ... 1st iteration (Swap 1st element into "buffer") 4,2,3,1 ... 2nd iteration (Permute subset) 4,1,3,2 ... 2nd iteration (Swap 2nd element into "buffer") 4,1,3,2 ... 3rd iteration (Permute subset) 4,1,2,3 ... 3rd iteration (Swap 3rd element into "buffer") 4,1,2,3 ... 4th iteration (P에르뮤트 서브셋) 4,1,2,3 ...4번째 반복 (스왑 4번째 원소를 "버퍼"로 입력) ...변경된 배열은 원본의 회전된 버전임

A의 경우 $n{\displaystyle }$= ${\displaystyle \mathrm{i}}$+ 1 ${\displaystyle n=i+1$}이$($가) 홀수인$$ 경우 첫 번째 i 요소에 대해 힙 알고리즘을 수행한 후 첫 번째 i 요소의 하위 집합이 회전한다.포루프를 1회 반복한 후 A에서 힙 알고리즘을 수행할 때 A가 1만큼 오른쪽으로 회전한다는 점에 유의하십시오.유도 가설에 의해 첫 번째 i 원소가 회전한다고 가정한다.이 회전 후, A의 첫 번째 요소는 버퍼로 교환되며, 이전 회전 연산과 결합하면 본질적으로 어레이에서 회전을 수행한다.이 회전 작업을 n번 수행하면 어레이가 원래 상태로 되돌아간다.이는 사례 $n{\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle n=5}$에 대해 아래에 설명되어 있다$.$

1,2,3,4,5 ...Original Array 4,1,2,3,5 ... 1st iteration (Permute subset/Rotate subset) 5,1,2,3,4 ... 1st iteration (Swap) 3,5,1,2,4 ... 2nd iteration (Permute subset/Rotate subset) 4,5,1,2,3 ... 2nd iteration (Swap) 2,4,5,1,3 ... 3rd iteration (Permute subset/Rotate subset) 3,4,5,1,2 ... 3rd iteration (Swap) 1,3,4,5,2 ... 4th iteration (Permute subset/Rotate subset) 2,3,4,5,1 ... 4차 반복(스왑) 5,2,3,4,1 … 5차 반복(Permute subset/Rotate subset) 1,2,3,4,5 … 5차 반복(스왑) …배열의 최종 상태는 원본과 동일한 순서로 되어 있다.

이제 클레임에 대한 유도 증명이 완료되었으며, 이는 힙스 알고리즘이 어레이 A의 모든 순열을 생성하는 이유로 이어질 것이다.우리는 다시 한번 힙 알고리즘의 정확성을 유도로 증명할 것이다.

기준: 힙의 알고리즘은 출력 A가 A의 유일한 순열이기 때문에 크기가 1인 어레이를 대수롭지 않게 허용한다.

유도:힙의 알고리즘이 크기 i의 배열을 허용한다고 가정하십시오.이전 증명의 결과를 이용하여, A의 모든 요소는 첫 번째 i 요소가 순열될 때 한 번 "버퍼"에 있게 된다.어레이의 순열은 요소 x를 A에서 제거한 다음 변경된 어레이의 각 순열로 x를 태킹하여 일부 어레이 A를 변경할 수 있으므로$,$ 힙의 알고리즘은 기본적으로 "$버퍼$"에 대해 제거된 요소를 고정하기 위해 크기 $i{\displaystyle }$+$1의 어레이$를 허용하고 permu에 고정한다$.$size i의 하위 배열의 tation.힙 알고리즘의 각 반복은 서브어레이션을 순열할 때 A가 버퍼를 점유하는 요소가 다르기 때문에, A의 각 요소가 버퍼 요소 없이 어레이 A의 순열에 태클될 기회가 있기 때문에 모든 순열은 생성된다.

빈번한 잘못 구현

재귀 호출의 예를 줄임으로써 위에 제시된 재귀 버전을 단순화하는 것이 유혹적이다.예를 들어 다음과 같다.

절차 발생시키다(k : 정수의, A : 배열하다 의 아무 것이나):     만일 k = 1 그때         생산량(A)     다른          // 각 k에 대해 한 번 반복 호출         을 위해 i := 0; i < k; i += 1 하다             발생시키다(k - 1, A)             // k(짝수 또는 홀수)의 패리티에 따라 스왑 선택 가능             만일 k 이다 짝수 그때                 // i == k-1일 때 no-op                 바꾸다(A[i], A[k-1])             다른                 // i==k-1일 때 XXX가 잘못된 추가 스왑                 바꾸다(A[0], A[k-1])              종지부를 찍다 만일          종지부를 찍다 을 위해     종지부를 찍다 만일 

이 구현은 모든 순열 생산에는 성공하지만 움직임을 최소화하지는 않는다.재귀적 콜스택이 풀리면서 각 수준에서 추가 스왑이 발생한다.Half of these will be no-ops of ${\displaystyle A[i]}$ and ${\displaystyle A[k-1]}$ where ${\displaystyle i==k-1}$ but when ${\displaystyle k}$ is odd, it results in additional swaps of the ${\displaystyle kth}$ with the ${\displaystyle 0th}$ element.

${\displaystyle n}$	${\displaystyle n!-1}$	스와프	추가 = 스왑${\displaystyle }$-${\displaystyle }$( ${\displaystyle n}$!${\displaystyle }$- ${\displaystyle 1}$) ${\displaystyle -(n!-1)}$
1	0	0	0
2	1	1	0
3	5	6	1
4	23	27	4
5	119	140	21
6	719	845	126
7	5039	5922	883
8	40319	47383	7064
9	362879	426456	63577

이러한 추가 스왑은 $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$ 접두사$$ 요소의 순서를 크게 변경한다.

추가 스왑은 루프 전에 추가 재귀 호출을 추가하고 $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$번$$(위의 $경우{\displaystyle }$) 또는 k ${\displaystyle k}$번$$ 반복하거나 i ${\displaystyle i}$이(가) 다음과 같이$$ $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$보다 작은지 확인함으로써 방지할 수 있다.

절차 발생시키다(k : 정수의, A : 배열하다 의 아무 것이나):     만일 k = 1 그때         생산량(A)     다른          // 각 k에 대해 한 번 반복 호출         을 위해 i := 0; i < k; i += 1 하다             발생시키다(k - 1, A)             // i==k-1일 때 스왑 방지             만일 (i < k - 1)                 // k의 패리티에 따른 스왑 선택                 만일 k 이다 짝수 그때                     바꾸다(A[i], A[k-1])                 다른                     바꾸다(A[0], A[k-1])                 종지부를 찍다 만일             종지부를 찍다 만일         종지부를 찍다 을 위해     종지부를 찍다 만일 

선택은 주로 미학적이지만 후자는 $i{\displaystyle }$ ${\displaystyle i}$의 값을 두$$ 배 더 자주 확인하는 결과를 낳는다.

참고 항목

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

참조