힙 알고리즘
힙(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)을 보여준다는 점에서 비교할만한 유용한 유사한 점도 있다.
같이 보기[편집]
참고[편집]
- ↑ Heap, B. R. (1963). “Permutations by Interchanges” (PDF). 《The Computer Journal》 6 (3): 293–4. doi:10.1093/comjnl/6.3.293.
- ↑ Sedgewick, R. (1977). “Permutation Generation Methods”. 《ACM Computing Surveys》 9 (2): 137–164. doi:10.1145/356689.356692.
- (스택 오버플로-자바스크립트, 순열)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