Algorithm Review 7

Printing Permutation

1. 알고리즘 원리

• {a, b, c, d}의 모든 순열을 구하는 방법은 다음과 같다.
  • 첫 원소가 a면서 {b, c, d}의 모든 순열
  • 첫 원소가 b면서 {c, d, a}의 모든 순열
  • 첫 원소가 c면서 {a, c, d}의 모든 순열
  • 첫 원소가 d면서 {a, c, b}의 모든 순열
    
    
• {b, c, d}의 모든 순열을 구하는 방법은 다음과 같다.
  • 첫 원소가 b면서 {c, d}의 모든 순열
  • 첫 원소가 c면서 {b, d}의 모든 순열
  • 첫 원소가 d면서 {a, c}의 모든 순열

Perm(prefix, S)의 Mission: S의 모든 순열을 구한 후 각 집합에 prefix를 붙여서 출력한다.

2. Puesdo Code

void printPerm(prefix, S)
{
	if S == ∅
    	print prefix
    else
    	for each first element x in S
        printPerm(prefix + x, S - x)
}

3. Code

void perm(k)
{
	if (k == n)
    	for (int i = 0; i < k; i++)
        	printf("%d ", data[i]);
    else
    	for (int i = k; i < n; i++){
        	// swap elements at index k and i in data
        	swap(data, k, i);
            prem(k+1);
            // return swapped elements to the right position
            swap(data, k, i);
        }
    
}

4. 코드의 귀납적 증명

1. 함수 perm(k)의 Mission은 모든 data[0...k-1]을 prefix로 하고, data[k...n-1]으로 모든 순열을 구한 후 prefix를 붙여 출력하되, 배열 data에 있는 원소의 순서는 그대로 유지하는 것이다.

2. Base case는 집합 S가 공집합인 경우 모든 data를 출력한다.

3. Recursive case에서 perm(k+1)이 1의 Mission을 수행한다고 가정 했을 때
   1) for에서 첫 번째 swap에 의해 모든 첫번 째 원소에 대하여
   2) perm(k+1)이 실행 된 후
   3) 다시 swap되면서 원소의 순서가 그대로 유지된다.

4. 따라서 1의 가정은 참이된다.

5. 재귀 함수와 상태공간트리

위와 같이 모든 경우의 수를 방문하는 것을 Enumeration이라고 한다. 이것은 상태공간트리의 모든 leaf 노드들을 방문하는 것과 같다.

이 문제를 상태공간트리로 표현하면 위와 같다.

• 각 노드는 prefix에 속한 집합을 의미하고
• Recursive Condition에서 for 루프와 swap 함수에 의해 각 노드 엣지의 방향이 정해진다.
• 그리고 perm(k+1)을 호출하면서 다음 노드로 이동하는 것이다.