재귀 알고리즘, 순열(permutation) 나열하기

n ≥1 개의 원소를 가진 집합이 주어졌을 때 이 집합의 모든 가능한 순열을 출력해보자. n 개의 주어진 원소에 대해 n! 개의 상이한 순열이 있음도 쉽게 알 수 있다. 4개의 원소 { a, b, c, d }로 된 집합을 살펴보면 간단한 알고리즘을 얻을 수 있다.

이에 대한 순열의 집합은 다음과 같이 출력시키면 결과를 얻을 수 있다. 1) a로 시작하는 { b, c, d }의 모든 순열 2) b로 시작하는 { a, c, d }의 모든 순열 3) c로 시작하는 { a, b, d }의 모든 순열 4) d로 시작하는 { a, b, c }의 모든 순열 ' ~로 시작하는 ~의 모든 순열 '이라는 표현이 바로 순열의 실마리이다. 이것은 n-1개의 원소에 동작하는 알고리즘이 있다면, n 개의 원소를 가진 집합에 대한 문제도 해결할 수 있음을 의미한다.

이러한 사고로부터 다음과 같은 프로그램을 만들 수 있다. 초기의 함수 호출은 permutation(arr, 0, n-1)이 된다.

#define ...