최근 수정 시각 : 2024-07-21 05:05:58

힙 알고리즘

힙 순열 알고리즘에서 넘어옴
1. 개요2. 힙 알고리즘의 순열 구조3. 스왑 알고리즘4. 예시
4.1. JavaScript4.2. 원소가 짝수개인 힙 알고리즘의 순열 구조4.3. 힙 알고리즘과 홀짝성
5. 관련 문서

1. 개요

1963년 B. R. 히프(B. R. Heap)[1]이 발표한 힙 순열 알고리즘(Heap Permutation algorithm)은 로버트 세지윅(Robert Sedgewick)이 재해석하기까지 거의 주목을 받지 못했다고 언급되고있다. 로버트 세지윅(Robert Sedgewick)에 따르면 힙 알고리즘(Heap algorithm)은 논리적 순열의 생성 구조에 기반한 저수준(low level)의 순열 생성 알고리즘이다. [2][3][4] 특히 힙 알고리즘은 넌재귀함수 알고리즘(non-recursive algorithm)으로 저수준이어서 CPU나 메모리에 부하가 적다. 따라서 가볍고 빠르다. 로버트 세지윅(Robert Sedgewick)이 1977년 제안한 바와 같이 현대 컴퓨터 프로그램 언어에서 순열 생성 알고리즘으로 개량된 버전들이 널리 사용되고 있다.[5][6]

2. 힙 알고리즘의 순열 구조

원소 3개인 힙 알고리즘 순열의 생성 순서의 예시
홀짝성(pairty) 스왑 지점 생성 규칙(교환(exchange)종류 2개)
0:짝(even) [math(\dot{1}\dot{2}3 \rightarrow \dot{2}\dot{1}3)] 첫째자리와 둘째자리 스왑핑(교체)
1:홀(odd) [math(\dot{2}1\dot{3}\rightarrow \dot{3} 1 \dot{2})] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{3} \dot{1}2 \rightarrow \dot{1} \dot{3}2 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{1}3 \dot{2} \rightarrow \dot{2} 3\dot{1} )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{2} \dot{3}1 \rightarrow \dot{3} \dot{2} 1)] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{3} 2\dot{1} \rightarrow \dot{1} 2\dot{3} )] 첫째자리와 세번째자리 스왑핑(swaping)
홀수개의 원소수(n) n!번에서 홀짝성에 따른 단2개의 교환(exchange)은 결국 다시 자기자신으로 돌아온다는 중요한 순열의 성질을 1963년 B. R. 힙(B. R. Heap)은 2페이지 분량의 짧은 자신의 논문에서 이를 자세히 그리고 간략하게 설명하고 있다.
첫째자리와 세번째자리 스왑핑(swaping)이라는 교환(exchange)은 원소 3개인 힙 알고리즘 순열의 생성 순서에서 원소2개인 힙 알고리즘 순열의 생성 순서 즉 첫째자리와 둘째자리 스왑핑(swaping)이라는 교환(exchange)에 기반한다.
따라서 첫째자리와 둘째자리 스왑핑(swaping)이라는 교환(exchange)과 첫째자리와 세번째자리 스왑핑(swaping)이라는 교환(exchange)을 기반으로 원소4개인 힙 알고리즘 순열의 생성 순서는 첫째자리와 네째자리 스왑핑(swaping)이라는 교환(exchange)구조가 논리적으로 추가 된다.

한편 첫째자리를 기준으로 하는 교환(exchange)이 성립하듯이 끝자리를 기준으로하는 힙 알고리즘도 동등하게 가능하다.

3. 스왑 알고리즘

.....
j = p[i];
p[i] = p[k];
p[k] = j;
.....
단 2개의 저장공간의 순서를 바꾸는 스왑 알고리즘(swap algorithm)의 스왑핑(swaping)은 추가적인 1개의 저장공간이 더 필요하다. 이렇게 3개의 공간이 저글링처럼 돌아간다.
A(1),B(2)를 서로 바뀌기 위해서는 A의 값 1을 C(□)에 먼저 옮겨서 저장한후 B의 2를 A(2)에 넣고 B에 C(1)을 넣는 식이다. 이렇게 하기 위해 C(□)가 임시 저장공간으로 중간과정에서 필요한 것이다.

한편 힙 알고리즘(algorithm)은 공교롭게도 스왑 알고리즘(swap algorithm)만있으면 재귀적으로 순열을 재배열할 수 있기에 따로 재귀함수가 필요 없다는 점에서 강력하다고 할 수 있다.

4. 예시

4.1. JavaScript

#!syntax javascript

  <script>
    function Heap(p) {
      var N = p.length ;
      var record = new Array();
      record.push(p.join(""));

      // 힙 알고리즘
      var c = new Array(N).fill(0, 0, N) ;
      var i=1,j, k;

      while (i <= N) {
        if (c[i] < i) {
          if (i % 2 == 0) {
            k = 0;
          }
          else {
            k = c[i];
          }

          // 스왑 알고리즘 비기닝
          j = p[i];
          p[i] = p[k];
          p[k] = j;

          // 스왑 알고리즘 엔딩
          c[i] = c[i] + 1;
          i = 1;
          record.push(p.join(""));

        }
        else {
          c[i] = 0;
          i = i + 1;
        }
      }
      return record;
    }

    window.onload = function () {
      document.write(Heap([1, 2, 3]));
    }
  </script>
</html>
(결과값) 123,213,312,132,231,321
1963년 B. R. 힙(B. R. Heap)이 제안하고 로버트 세지윅(Robert Sedgewick)등이 개량한 힙 순열 알고리즘의 자바스크립트 버전 [7][8]

4.2. 원소가 짝수개인 힙 알고리즘의 순열 구조

원소 4개인 힙 알고리즘 순열의 생성 순서의 예시
홀짝성(pairty) 스왑 지점 생성 규칙(교환(exchange)종류 2개)
0:짝(even) [math(\dot{1}\dot{2}34 \rightarrow \dot{2}\dot{1}34 )] 첫째자리와 둘째자리 스왑핑(교체)
1:홀(odd) [math(\dot{2}1\dot{3}4\rightarrow \dot{3} 1 \dot{2}4 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{3} \dot{1}24 \rightarrow \dot{1} \dot{3}24 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{1}3 \dot{2}4 \rightarrow \dot{2} 3\dot{1}4 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{2} \dot{3}14 \rightarrow \dot{3} \dot{2} 14 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{3} 21 \dot{4} \rightarrow \dot{4} 21 \dot{3} )] 첫째자리와 네번째자리 스왑핑(swaping)
0 [math(\dot{4} \dot{2}13 \rightarrow \dot{2} \dot{4} 13 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{2} 4\dot{1}3 \rightarrow \dot{1} 4\dot{2}3 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{1} \dot{4}23 \rightarrow \dot{4} \dot{1} 23 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{4} 1\dot{2}3 \rightarrow \dot{2} 1\dot{4}3 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{2} \dot{1}43 \rightarrow \dot{1} \dot{2} 43 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math( 1\dot{2}4\dot{3} \rightarrow 1\dot{3} 4\dot{2} )] 두번째자리와 네번째자리 스왑핑(swaping)
0 [math(\dot{1} \dot{3}42 \rightarrow \dot{3} \dot{1}42 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{3}1\dot{4}2 \rightarrow \dot{4}1\dot{3}2 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{4} \dot{1}32 \rightarrow \dot{1} \dot{4}32 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{1} 4\dot{3}2 \rightarrow \dot{3} 4\dot{1}2 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{3} \dot{4}12 \rightarrow \dot{4}\dot{3}12 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(43\dot{1}\dot{2} \rightarrow 43\dot{2}\dot{1} )] 세번째자리와 네번째자리 스왑핑(swaping)
0 [math(\dot{4} \dot{3}21 \rightarrow \dot{3} \dot{4}21 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{3}4\dot{2}1 \rightarrow \dot{2}4\dot{3}1 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{2} \dot{4}31 \rightarrow \dot{4} \dot{2}31 )] 첫째자리와 둘째자리 스왑핑(교체)
1 [math(\dot{4} 2\dot{3}1 \rightarrow \dot{3} 2\dot{4}1 )] 첫째자리와 세번째자리 스왑핑(swaping)
0 [math(\dot{3} \dot{2}41 \rightarrow \dot{2}\dot{3}41 )] 첫째자리와 둘째자리 스왑핑(교체)
홀수개의 원소를 갖는 힙 알고리즘의 순열 생성 순서와 짝수개의 원소를 갖는 힙 알고리즘의 순열 생성 순서는 비교될수 있게 다르다. 그러나 동일한 순열의 홀짝성(pairty)하에서 작동하고 또한 같은 스왑 알고리즘에 기반하고 있기때문에 짝수개의 원소를 갖는 힙 알고리즘의 순열 생성 순서가 좀더 복잡해지는듯 보인다.

한편 홀수개의 원소수(n) n!번에서 홀짝성에 따른 단2개의 교환(exchange)은 결국 다시 자기자신으로 돌아온다는 중요한 순열의 성질에서 짝수개의 원소를 갖는 힙 알고리즘의 순열 생성 순서는 중간중간에 다시 자기자신으로 돌아가지 않기위해(중단회피) 터닝포인트를 설정해줌으로써 n개의 원소수 순열은 n!개의 힙 알고리즘을 완전하게 생성을 끝낼수있다.

4.3. 힙 알고리즘과 홀짝성

순열의 홀짝성(pairty)에서 n개의 원소를 갖는 n! 힙 알고리즘의 순열 생성 순서는 [math( n = 2 \rightarrow \infty )]에서 (n-1)!의 재귀적으로 순환되는 꼬임으로 완성된다.
이러한 사실을 조사할수있는 좋은 예로서 4! 힙 알고리즘의 순열 생성 순서가 3! 순열 생성 순서로 잘 짜여지는 것을 보여준다는 점에서 4개의 원소를 갖는 짝수개 힙 알고리즘 순열 생성 순서로 부터 n-1의 홀수개 순열생성순서와 n+1의 홀수개 순열생성순서를 쉽게 확인할수있다.

5. 관련 문서

[1] 외래어 표기법에서는 장음 뒤의 파열음은 ㅡ를 붙여서 표기하는 것이 원칙이나, Heap를 '힙'으로 쓰는 경우가 압도적으로 많다.[2] article Free Access, Algorithm 115: Perm, Author: H. F. Trotter, Communications of the ACM, Volume 5 Issue 8 Aug. 1962 pp 434–435 doi:10.1145/368637.368660 Online:01 August 1962 Publication History https://dl.acm.org/doi/10.1145/368637.368660[3] journal article, Generation of Permutations by Adjacent Transposition, Selmer M. Johnson, Mathematics of Computation, Vol. 17, No. 83 (Jul., 1963), pp. 282-285 (4 pages), Published By: American, Mathematical Society, Mathematics of Computation, doi:10.2307/2003846 https://www.jstor.org/stable/2003846[4] Permutations by interchanges By B. R. Heap, The Computer Journal, Volume 6, Issue 3, November 1963, Pages 293–298, https://doi.org/10.1093/comjnl/6.3.293 Published:01 November 1963[5] article Free Access, Permutation Generation Methods, Author: Robert Sedgewick, ACM Computing Surveys, Volume 9 Issue 2. June 1977 pp 137–164 https://doi.org/10.1145/356689.356692 Online:01 June 1977 Publication History[6] 러스트(Rust) -permutohedron() https://docs.rs/permutohedron/latest/permutohedron/ heap_recursive: Heap's algorithm for generating permutations, recursive version.[7] Computing Surveys, Col 9, No 2, June 1977 ,Permutation Generation Methods,P143 ,ROBERT SEDGEWlCK ,Program ~n Computer Science and Dwlsmn of Applled Mathematics ,Brown Unwersity, Prowdence, Rhode Island 02912 https://dl.acm.org/doi/pdf/10.1145/356689.356692[8] (stackoverflow) Permutations in JavaScript? https://stackoverflow.com/questions/33114851/johnson-trotter-permutation

분류