힙 알고리즘
힙(Heap)의 알고리즘은 n개체의 가능한 모든 순열을 생성한다. 1963년 힙(B.R. Heap)에 의해 처음 제안되었다.[1]이 알고리즘의 주요한 특징은 움직임을 최소화한다는 것이다. 단일 요소 쌍을 교환하여 이전 순열에서 각 순열을 생성함으로써 이러한 결과를 갖을수있다. 다른 n-2 요소는 방해받지 않는다. 순열 생성 알고리즘에 대한 1977년 검토에서 로버트 세지윅(Robert Sedgewick)은 당시 컴퓨터로 순열을 생성하는 데 가장 효과적인 알고리즘이라고 결론지은바있다.[2]
힙의 알고리즘에 의해 생성된 n개 객체의 순열 시퀀스는 n + 1 객체의 순열 시퀀스의 시작이다. 따라서 힙(Heap) 알고리즘(OEIS의 시퀀스 A280318)에 의해 생성된 무한 시퀀스의 순열이 계산된바 있다.
예
n(3)개의 원소를 갖는 집합에서의 순열의 경우의 수를 보여주는 힙 알고리즘을 사용한 자바스크립트 프로그램
<html><script>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]));}</script></html>- 결과 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