순열 permutation

순열문제( Permutation)

주어진 입력 n에 대하여 1 부터 n까지의 수들의 모든 수들을 나열하여 출력하는 프로그램을

작성하는 문제이다.

1, 2, 3의 순열은 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지이다.

n=4 일경우 출력:
-----------------------------------------
1 2 3 4 1 이 앞에 있는 경우
1 2 4 3 1 이 앞에 있는 경우
1 3 2 4 1 이 앞에 있는 경우
1 3 4 2 1 이 앞에 있는 경우
1 4 2 3 1 이 앞에 있는 경우
1 4 3 2 1 이 앞에 있는 경우
-----------------------------------------
2 1 3 4 2 가 앞에 있는 경우
2 1 4 3 2 가 앞에 있는 경우
2 3 1 4 2 가 앞에 있는 경우
2 3 4 1 2 가 앞에 있는 경우
2 4 1 3 2 가 앞에 있는 경우
2 4 3 1 2 가 앞에 있는 경우
-----------------------------------------
3 1 2 4 3 이 앞에 있는 경우
3 1 4 2 3 이 앞에 있는 경우
3 2 1 4 3 이 앞에 있는 경우
3 2 4 1 3 이 앞에 있는 경우
3 4 1 2 3 이 앞에 있는 경우
3 4 2 1 3 이 앞에 있는 경우
-----------------------------------------
4 1 2 3 4 가 앞에 있는 경우
4 1 3 2 4 가 앞에 있는 경우
4 2 1 3 4 가 앞에 있는 경우
4 2 3 1 4 가 앞에 있는 경우
4 3 1 2 4 가 앞에 있는 경우
4 3 2 1 4 가 앞에 있는 경우
-----------------------------------------

이 문제도 순환호출이 자연스럽게 쓰이는 경우라고 할 수 있다.
n=4의 경우를 잘 관찰해 보면 전체 출력이 4개의 부분으로 나뉘는 것을 알 수 있다.
1이 앞에 나오는 경우가 6가지이고 2, 3, 4가 앞에 나오는 경우가 각각 6가지씩이다.

4가 앞에 나오는 경우를 보면 4를 제외한 나머지 부분은 1, 2, 3을 순서대로 나열했을
때와 같음을 알 수 있다. 마찬가지로 1이 앞에 나오는 경우도 2, 3, 4를 순서대로 나열한
것과 같다.

주어진 n개의 수들을 나열하는 방법은 n개들의 수들이 앞에 나오는 n가지의 경우로
나누어진다. 각각의 경우에는 n-1개의 수들을 나열하여 앞의 수에 더하여 출력하면 된다.

Factorial(n) = n * Factorial(n-1)

위의 식을 이용하여 순열문제를 풀 수가 있다.

순열문제를 풀 때 고민이 되는 부분은 이미 뽑은 자료들과 앞으로 뽑아야 하는 자료들을
어떻게 나타내야 하는 것이다. 메인 함수에서 호출할 때 두 개의 배열을 따로 사용해서
호출을 하도록 하면 되겠다.

순환함수 내에서는 따로 두 개의 배열을 잡아서 하위 순환호출을 할 때 사용하면 되겠다