Swap을 사용한 순열 구하기

참고 문서

• 이 블로그의 문서: DFS를 사용한 순열 구하기
• GitHub: 이 프로젝트의 리포지토리(algorithm)

이 문서의 내용

순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다.

예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다.

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

Swap이란?

Swap은 배열에서 두 개 요소의 위치를 서로 바꾸는 것을 의미합니다.

static void swap(int[] arr, int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

요소의 위치를 서로 바꾸기 위해 먼저 덮어씌워지는 요소는 임시 변수에 저장됩니다.

Swap을 사용한 순열 흐름도

Swap을 재귀적으로 호출하면서 배열의 원소의 위치를 계속 변경합니다.

원소의 위치 변경은 깊이(depth)가 0부터 시작해서 배열의 크기만큼 진행될 때까지 진행됩니다.

변경된 배열은 더 이상 진행될 수 없을 때 수열에서의 하나의 경우의 수가 됩니다.

예시의 흐름도에서 depth = 3의  1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 2, 1 3, 1, 2 6개의 경우의 수가 발생합니다.

Swap을 사용한 순열 계산의 특징은 순열의 순서가 보장되지 않는다는 점입니다.

흐름도에서 마지막 2개 순열의 기대값은 3, 1, 2와 3, 2, 1이지만 실제로는 다음과 같이 표시됩니다.

[3, 2, 1]
[3, 1, 2]

Swap을 사용한 순열 구현

순열을 계산하기 위한 인자는 arr depth r입니다.

depth의 초기 값은 0으로 시작합니다. r은 주어진 배열에서 몇 개의 수를 뽑아낼 것인가를 의미합니다.

public class Swap
{
	protected static void permutation(int[] arr, int depth, int r)
	{
		if (depth == r)
		{
			printResult(arr, r);
			return;
		}
		
		for (int i = depth; i < arr.length; ++i)
		{
			// 현재 인덱스와 뒤의 요소를 스왑
			swap(arr, depth, i);
			// depth를 한 칸 이동
			permutation(arr, depth + 1, r);
			// 현재 인덱스와 뒤의 요소를 스왑(원위치)
			swap(arr, depth, i);
		}
	}
	
	static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

코드		비고
Line 5:9	if (depth == r)	depth가 r에 도달하면 하나의 경우의 수가 발생합니다.
Line 11	for (i = depth; i < arr.length; ++i)	현재 depth에서 Swap을 진행합니다. 이때 depth에 해당하는 인덱스 이하는 고정입니다.
Line 14	swap(arr, depth, i)	현재 인덱스와 뒤의 요소를 Swap합니다.
Line 16	permutation(arr, depth + 1, r)	depth를 한 칸 이동하고 재귀적으로 다음 단계를 진행합니다.
Line 18	swap(arr, depth, i)	Line 14의 Swap을 원위치로 돌이킵니다.