7.1 순열 알고리즘

바구니에 있는 여러 개의 공을 꺼내는 순서의 조합을 찾는 것은 대표적인 순열 문제입니다. 그리고 확률과 통계를 얘기할 때도 순열 문제는 자주 등장합니다.

바구니에서 공을 꺼내는 문제에서는 바구니에 남아있는 공과 꺼낸 공의 조합이 경험정보입니다. 이러한 경험 정보를 스택을 이용하여 동적 알고리즘으로 해결하면 어렵지 않게 문제를 해결할 수 있습니다. 하지만 모든 경험을 수행해야 하기 때문에 단계가 많고 현재 단계에서 다음 단계로 진행할 수 있는 가지 수가 많을 때 수행 속도가 무리하게 커질 수 있는 문제점도 갖고 있습니다.

여기에서 구현할 예는 바구니에 서로 다른 숫자가 써 있는 공이 있을 때 n개의 공을 하나씩 꺼내는 예로 할게요. 이 때 꺼낸 순서를 포함하여 나올 수 있는 모든 경우를 조사하기로 합시다.

먼저 바구니에는 0부터 9까지 숫자가 쓰여있는 공이 있습니다. 그리고 이 상태에서 발생할 수 있는 다음 상태는 0번 공을 꺼냈을 때부터 9번 공을 꺼냈을 때까지 10가지 경우가 발생합니다. 만약 0번 공을 꺼냈다면 바구니에는 1에서 9번 공이 들어있겠죠. 이렇게 초기 상태에서 발생할 수 있는 10개의 다음 상태를 스택에 보관합니다.

그리고 스택에서 하나의 상태를 얻어옵니다. 예를 들어 0번 공을 꺼내고 1에서 9번 공이 바구니에 있는 상태를 얻어왔다고 가정합시다. 이 상태에서 발생할 수 있는 다음 상태는 1번 공을 꺼냈을 때부터 9번 공을 꺼냈을 때까지 9가지 경우가 발생합니다. 만약 1번 공을 꺼냈다면 0번, 1번 순으로 공을 꺼냈고 2번에서 9번 공이 바구니에 들어있겠죠. 이렇게 조사한 다음 상태가 종료 조건에 도달하였는지 확인하여 도달하면 이를 결과로 출력하고 그렇지 않을 때만 스택에 보관합니다. 이와 같은 동작을 스택이 빌 때까지 수행하면 전체 문제를 해결할 수 있습니다.