순열 (Permutation) 구현

1. 순열이란?

순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
예를들어 [1,2,3] 수열이 있을경우 이에 대한 순열은 다음과 같이 6가지가 있다.

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

2. 순열의 구현 (Next Permutation)

순열을 구현하는데는 다음과 같은 2가지 방식만 알아놓으면 좋을 것 같다.

1. iterative한 방법
2. recursive한 방법

Recursive한 방법

DFS + 방문처리를 이용한 방식으로 순열을 구하는 과정에서 추가적인 조건을 적용하기 좋다.

public static void permutation(int idx) {
	if (idx == R) {
    	System.out.println(result);
    	return;
    }
    for (int i = 0; i < list.length; i++) {
    	if (visited[i]) continue;
        result[idx] = list[i];
        visited[i] = true;
        permutation(idx+1);
        visited[i] = false;
    }
}

Iterative한 방법

C++에는 STL로 next_permutation 알고리즘을 그대로 사용가능하지만, 자바에서는 직접 구현해서 사용해야한다. 특징은 while문을 통해 next_permutation을 반복하는 것인데 특정 상태에서 다음 상태를 구하는데 용이하고 추가적인 메모리를 사용하지 않아도 된다(in place).

Permutation

public static void permutation() {
    while (nextPermutation(list)) {
    	System.out.println(list);
    }
}

next_permutation

오름차순으로 정렬된 수열에 대하여 내림차순으로 바꾸는 과정에서 현재 다음 수열의 상태로 바꿔주는 것.

1. list(수열)에 대해서 list[i-1] < list[i]를 만족하는 가장 큰 수를 찾는다. 
2. 1번에서 찾은 i-1에 대하여 list[i-1] < list[j]를 만족하는 가장 큰 j를 찾는다.
3. list[i-1], list[j]를 swap한다. 
4. list[i ... n-1]을 reverse 시킨다. 

void reverse(int[] list,int i,int n){
    for(;i<n;) swap(list[i++],list[n--]); 
}
bool nextPermutation(int[] list)
{
    int i, j;
    i = j = list.length-1;
    while (list[i - 1] >= list[i]) if (--i== 0) return false;
    while(list[j]<=list[i-1]) if(--j==0) return false; 
    swap(list[j],list[i-1]);
    reverse(list,i,list.length-1);
    return true;
}