힙 알고리즘

힙(Heap)의 알고리즘은 n개체의 가능한 모든 순열을 생성한다. 1963년 힙(B.R. Heap)에 의해 처음 제안되었다.이 알고리즘의 주요한 특징은 움직임을 최소화한다는 것이다. 단일 요소 쌍을 교환하여 이전 순열에서 각 순열을 생성함으로써 이러한 결과를 갖을수있다. 다른 n-2 요소는 방해받지 않는다. 순열 생성 알고리즘에 대한 1977년 검토에서 로버트 세지윅(Robert Sedgewick)은 당시 컴퓨터로 순열을 생성하는 데 가장 효과적인 알고리즘이라고 결론지은바있다.

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

예
n(3)개의 원소를 갖는 집합에서의 순열의 경우의 수를 보여주는 힙 알고리즘을 사용한 자바스크립트 프로그램
   function permute(permutation) {
  var length = permutation.length ;
  var    result =   permutation.slice()  ;
  var    c = new Array(length).fill(0) ;
   var   i = 1, k, p;
  while (i < length) {
    if (c[i] < i) {
      k =  i%2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      c[i]++;
      i = 1;
      result.push(  permutation.slice());
    } else {
      c[i] = 0;
      i++;
    }
  }
  return result;
 }
 window.onload = function () {
 document.write(permute([1, 2, 3]));
 }


결과 1,2,3, 2,1,3, 3,1,2, 1,3,2, 2,3,1, 3,2,1

힙정렬
힙(Heap)알고리즘은 힙정렬(heap sort)과 다르지만 다른 n-2 요소는 방해받지 않는다는 스왑 알고리즘(swap algorithm)을 보여준다는 점에서 비교할만한 유용한 유사한 점도 있다.

 같이 보기 
 스테인하우스-존슨-트로터 알고리즘
 이진힙

 각주 

(스택 오버플로-자바스크립트, 순열)https://stackoverflow.com/questions/9960908/permutations-in-javascript
(Permutations by Interchanges , B. R. Heap , The Computer Journal, Volume 6, Issue 3, November 1963, Pages 293–298, DOI https://doi.org/10.1093/comjnl/6.3.293  , Published: 01 November 1963)https://academic.oup.com/comjnl/article/6/3/293/360213
(Permutation Generation Methods ,ROBERT SEDGEWlCK ,Program ~n Computer Science and Dwlsmn of Applled Mathematics
Brown Unwersity, Prowdence, Rhode Island 02912)http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf

분류:조합 알고리즘
분류:순열