순열(Permutation) 알고리즘

1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자

1-2-3

1-3-2

2-1-3

2-3-1

3-1-2

3-2-1

여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다.

1-2-3-4

1-2-4-3

1-3-2-4

1-3-4-2

....

4-3-2-1

이렇게 숫자를 뒤에서부터 섞으면, 훌륭한 순열의 모든 경우를 구할수 있다. 그렇다면 이를 알고리즘으로 어떻게 구현할 것인가? 은근히 골이 땡겨온다.

출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/

이럴때는 위의 그림을 한번 보다. ABC의 알파벳을 재귀적으로 푸는 방법이다. ABC 중 첫번째 알파벳을 뭘로 할것인가. 종류는 세가지밖에 없다. 처음을 배열은 ABC 순서로 정해져 있다.

A

B

C

위와같은 경우에서 첫번째가 A인 경우는 첫번째[0] 인자인 A를 첫번째[0] 인자 A와 바꾼것이나 다름이 없다. 물론 실질적으로는 바뀌는게 없겠지만, 바로 다음

첫번째 인자가 B로 설정되어있는 경우는 첫번째[0] 인자인 A를 두번째[1] 인자 B와 바꾼것이다.

세번째 인자가 C로 설정되어있는 경우는 첫번째[0] 인자인 A를 세번째[2] 인자 C와 바꾼것이다.

이제, 뭔가 반복문의 가능성이 보이기 시작한다. 트리구조의 맨 처음 부분은 이렇게 인자가 바뀌고 있다.

[0] <-> [0]

[0] <-> [1]

[0] <-> [2]

이제 첫번째 인자가 고정되었으니, 두번째 인자와 세번째 인자에 대해 고민을 할 필요가 있다. 위와 정확히 마찬가지로 같다.

[0] <-> [0] 이경우에 한해, 즉, A인 경우,

[0][1] <-> [0][1]   즉, 두번째 인자 [1] 인 B와 두번째 인자 [1] 인 B를 바꾼다. A B C

[0][1] <-> [0][2]   즉, 두번째 인자 [1] 인 B와 세번째 인자 [2] 인 C를 바꾼다. A C B

자 이제 마지막 경우를 살펴본다.

[0][1] <-> [0][1] 이경우에 한해,

[0][1][2] <-> [0][1][2]   즉, 바뀌는건 없다. A B C

[0][1] <-> [0][2] 이경우에 한해,

[0][2][1] <-> [0][2][1]   즉, 바뀌는것은 없다. A C B

이제 A에 대한 경우를 모두 살펴봤으므로, 다시 처음으로 돌아가서

[0] <-> [1] 의 경우를 위와같이 풀면 된다. 이러한 방향으로 알고리즘을 재귀적으로 짠다면, 참고 그림과 같이 ABC, ACB, BAC, BCA, CBA, CAB 순으로 튀어나오게 될것이다.

nPk 의 순열을 구해야 하는문제, 즉 n개중 k개로 이루어진 순열을 구하려고 한다. 샘플에서는 1,2,3,4 네개로 이루어진 배열을 가지고 4개로 이루어진 순열을 구해보고자 한다.

다음과 같은 시그니처를 사용해본다.

perm(int[] arr, int depth, int n, int k)

배열 arr 은 계속해서 데이터를 들고다니면서 교환되고 있는 배열이다.

depth 는 현재 트리구조에서 어떤 깊이에서 교환작업을 하고있는지에 대한 변수이다. 즉, 맨처음 깊이라면 0의 위치에서 작업하고 있을것이며 이는

첫번째와 첫번째 인자를 교환하거나(1,2,3,4) 

첫번째와 두번째 인자를 교환(2,1,3,4)하거나,

첫번째와 세번째(3,2,1,4) 인자를 교환하거나

첫번째와 네번째(4,2,3,1) 인자를 교환하는 중이다.

아래로 죽 내려서 최종결과를 참고해보고 이와같은 순서로 컴퓨터가 교환하고 있는지 확인해보면 아항 그렇구나라고 느끼게 된다. 물론 프로그램은 재귀적으로 계속 깊이 탐색되므로, depth는 0에대한 것을 다끝마치고 1로 넘어가는 것이 아니라 0,1,2,3,2,3,1,2,3 과 같은 형태로 내부적으로 변하고 있다. 물론 프로그램의 시작점에서는 0으로 넣어주어야 한다.  

n은 총 배열안에 들어있는 숫자를 뜻하며 고정값이다. 샘플은 1,2,3,4 네개이므로 4로 고정된다.

k는 몇개를 뽑아내서 순열을 만들것인지를 뜻하며 고정값이다. 샘플은 1,2,3,4 모두를 사용해 순열을 만드므로 4로 고정된다.

실제적인 구현은 아래와 같다.

	public void perm(int[] arr, int depth, int n, int k) {

		if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
			print(arr);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, i, depth);
			perm(arr, depth + 1, n, k);
			swap(arr, i, depth);
		}
		
	}

일단, depth를 검사해 k와 같으면 더이상 순열을 만들지 않는다. 우리가 원하는건 k개의 숫자가 있는 순열이기 때문이다. 4에 도달하면 출력해야하는 숫자 네개가 모두 세팅되었다는 뜻이므로 출력만 해주면 된다. 

depth에 따라서 for문의 시작점이 다르다. depth 가 0이라면 1XXX, 2XXX, 3XXX, 4XXX를 뽑아줘야 하기때문에 총 네번의 루프가 돌아야 하며 이는 i < n이라는 조건에서 n은 4로 고정이고 i는 depth에 따라 0부터 시작하기 때문에 0,1,2,3 네번이 도는것이다. 다만,

 

(depth 0) 1XXX이 만들어지면,

(depth 1) 2XXX를 만드는것이 아니라 12XX 13XX 14XX 를 만들고

(depth 2) 바로 다음으로 123X

(depth 3) 마지막으로 1234이 채워져지며

(depth 4) 출력한다.

 

perm(arr, depth + 1, n, k) 함수에 perm({1,2,3,4}, 4, 4, 4) 인자가 채워져서 호출된다. 그렇지만, depth는 이제 k와 같으므로 바로 return을 통해, perm문을 끝내고 다음 문장인 swap()을 실행하게 된다.

마지막으로 의문인 점은 왜 도대체 swap()함수를 두번 호출하느냐에 직관이 안생길수 있다. 이걸 동네미용실에서 머리자르면서 어떻게 설명할까 생각해려 했는데 메이플스토리 만화책을 보느라 생각을 못했다.

swap()함수를 두번쓰는것은 별로 깔끔해보이지 않는다, 그럼에도 불구하고 swap()함수는 꼭 필요하다. 재귀함수를 쓰면서 어쨌거나 perm() 함수에 자꾸 걸려서 뒤쪽swap()은 호출하지도 못하고 depth만 깊어지고 있는 도중 depth가 최종적으로 4가되면 perm()아래의 swap()함수가 드디어 호출된다. 바로, 두번째 swap()함수는 이지점에서 중요한 역할을 한다.

생각을 해보면, 함수는 투명해야한다. 포인터를 피해야하는 이유도 여기에 있다. 이 개념은 무엇인지 잘 안와닿으면, 1월달에 스칼라 책이 출간되니 한번 사서 보도록 한다. 리플을 달면 선착순 한권 준다. 아무도 관심없겠지만.. 마치 회사에서의 나처럼.허어엉허헣

근데 어쨌든 여기서는 swap()함수가 내부적으로 외부의 값들을 막 바꾸고 있다. perm()의 depth가 4가되어 한번 돌때마다 arr가 내부적으로 가지고있는 배열의 순서는 바뀌어져있다.

두번째 swap()은 전단계의 분기점에서의 배열의 순서를 기억하고 이를 초기화하는 작업에 지나지 않는다. 트리구조에서 depth는 0,1,2,3,2,3,1,2,3 뭐 이런식으로 한칸 두칸 뒤로 돌아가면서 다시 계산을 하는데 그 지점에서의 배열 안의 숫자 순서를 기억하고 있어야 한다. swap()없이 바로 사용하고자 한다면, 분기로 돌아가서 다시 교환을 하는게 아니라 이미 다른 분기에서 망가뜨려버린 배열의 순서를 그대로 이용하게 된다. 결론적으로 황당한 순열들이 마구 튀어나오게 된다.

ps) 본 프로그램은 준비작업적 함수를 두개를 만들어준다.

1) 배열의 특정위치를 교환하는 함수 (필수)

2) 배열을 출력하는 함수 (선택)

배열의 특정위치를 교환하는 함수가 필요한 이유는, c같은 경우는 포인터가 있어 주소값을 바로 찾아서 바꿔버릴수 있어 조금 더 편리하게 값들을 바로 바꿀수 있는 반면,

다른 언어들은 주소에 직접 접근하지 않고 참조형 변수로 접근하거나, 배열자체를 전달해 이의 값을 바꾸도록 하기 때문이다. 그렇다고 포인터를 남발하면 남발할수록 프로그램은 파악하기도 어렵고 버그가 자주 나니 지양하는 편이 낫다.

배열의 특정위치를 교환하는 함수는 다음과 같다. 이렇게 교환을 하면 굳이 포인터를 넘기지 않아도 알아서 배열안에 있는 값들이 교환된다. 다만 리턴값이 없기 때문에 이러한 프로그램 방식은 좋지 않다.보통, 함수는 외부의 다른 값을 바꾸는 것보다는, X -> Y 처럼 참조투명하게 작성하는 편이 훨씬 좋다. 다만, 여기서는 특정목적상 이렇게 쓰는 편이 머리굴리기는 낫다.

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

배열을 출력하는 함수는 중요하지 않으니 그냥 대충 맘대로 만든다.

	public void print(int[] arr, int k) {
		for (int i = 0; i < k; i++) {
			if (i == k - 1) System.out.println(arr[i]);
			else System.out.print(arr[i] + ",");
		}
	}

마지막으로 최종출력값은 다음과 같다.

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,3,2
1,4,2,3
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,3,1
2,4,1,3
3,2,1,4
3,2,4,1
3,1,2,4
3,1,4,2
3,4,1,2
3,4,2,1
4,2,3,1
4,2,1,3
4,3,2,1
4,3,1,2
4,1,3,2
4,1,2,3

최종적인 자바에서 활용되는 코드는 다음과 같다.

	
package algo;

public class Permutation {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4 };
		perm(arr, 0, 4, 4);
	}

	public static void perm(int[] arr, int depth, int n, int k) {

		if (depth == k) { // 한번 depth 가 k로 도달하면 사이클이 돌았음. 출력함.
			print(arr,k);
			return;
		}

		for (int i = depth; i < n; i++) {
			swap(arr, i, depth);
			perm(arr, depth + 1, n, k);
			swap(arr, i, depth);
		}

	}

	// 자바에서는 포인터가 없기 때문에 아래와 같이, 인덱스 i와 j를 통해 바꿔줌.
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void print(int[] arr, int k) {

		for (int i = 0; i < k; i++) {
			if (i == k - 1)
				System.out.println(arr[i]);
			else
				System.out.print(arr[i] + ",");
		}
	}

}