010 모든 순열 생성

순열과 관련된 문제는 흔히 재귀(recursivity)를 포함한다. 기본적으로 재귀는 어떤 시작 상태(initial state)가 주어지고 앞선 상태에 따라 각 연속된 상태(successive state)를 정의하는 하나의 프로세스로 정의된다.

모든 순열을 생성하는 문제에서는 주어진 문자열의 글자들로 상태를 나타낼 수 있다. 시작 상태는 최초의 문자열을 포함하며 연속된 각 상태는 다음 공식으로 계산한다. 문자열의 각 글자가 그 문자열의 첫 번째 글자가 되고(위치를 뒤바꾼다) 재귀 호출로 나머지 글자들을 뒤바꾼다. 재귀가 아닌 해법 혹은 다른 재귀 해법도 있으나 이 해법이 고전적이다.

ABC라는 문자열에 위 해법을 적용하면 다음과 같이 수행된다(순열이 어떻게 만들어지는지 보자).

▲ 그림 1-1