순열(permutation) 알고리즘

순열(permutation)이란 숫자나 문자들의 집합(set)에 순서를 부여하여 나열하는 것이라고 생각하면 된다.

예를들어 원소가 'A', 'B', 'C'를 가진 집합 S 가 있다면 ( { 'A', 'B', 'C' }  ∈ S) 이 A ,B, C 각각의 원소를 일렬로 나열했을때 나올수 있는 경우의 수는 (A, B, C), (A, C, B), (B, A, C), (B, C, A), (C, A, B), (C, B, A) 총 6가지가 나올수 있다.
순열에 대해서 자세히 알고 싶으면 순열(permutation) 를 먼저 읽어봐라.

 

그럼 순열을 프로그래밍적으로 어떻게 접근해야 할까?
만약 {a,b,c,d}의 모든 순열을 구한다고 하면 

☞ 첫 원소가 a이면서 {b,c,d}의 모든 순열 
☞ 첫 원소가 b이면서 {a,c,d}의 모든 순열 
☞ 첫 원소가 c이면서 {a,b,d}의 모든 순열 
☞ 첫 원소가 d이면서 {a,b,c}의 모든 순열을 구하면 된다.

 

위에 패턴을 정리하면 집합 S={a,b,c}의 모든 순열을 출력하려면 S의 각 원소 x에 대해서 S-{x}의 모든 순열들을 생성한 다음 각각의 맨 앞에 x를 추가해서 출력하면 되는 것이다.

 

좀 풀어 쓰면 {a,b,c} 수열에서 맨앞에 나열될 수 있는 것은 a, b, c 3가지이다. 
a, b, c 가 하나씩 앞으로 이동시키기 위해서 서로 swap 을 해주면된다. 
예를들어 a, b 를 swap 하여 { b, a, c} 그리고 a, c 를 swap 하여 { c, b, a} 3가지가 나온다.
그리고 맨앞에 나올수 있는 수는 다 나왔으니 이제 맨앞의 원소 {x} 빼고 나머지에 대해서도 동일한 것을 수행한다. 

{a, b, c} -> {a} 를 빼고 { b, c} 에 대해서 서로 swap 하면 { c, b} -> {a} + { c, b}
{b, a, c} -> {b} 를 빼고 { a, c} 에 대해서 서로 swap 하면 { c, a} -> {b} + { c, a}
{c, b, a} -> {c} 를 빼고 { b, a} 에 대해서 서로 swap 하면 { a, b} -> {c} + { a, b}

그림1.은 위 에 설명한 방법을 상태공간트리로 표현한 것이다.

그림1. A,B,C 순열을 위한 상태공간트리

[출처] https://www.geeksforgeeks.org/permutations-of-a-given-string-using-stl/

 
public class PermutationMain {
 
 
    public static void permute(char[] str, int l, int r)  {
        if (l == r) {
            System.out.println(String.valueOf(str));
        }
        else {
            for (int i = l; i <= r; i++) {
                swap(str,l,i);
                permute(str, l+1, r);
                swap(str,l,i);
            }
        }
    }
 
    public static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
 
    public static void main(String[] args) {
        char[] str = { 'A', 'B', 'C' };
        int n = str.length;
 
        permute(str, 0, n-1);
    }
    
}
 

permute 다음에 다시 swap 을 해주었는데 이것은 permute 전에 수행했던 swap 의해 순서가 뒤바껴 있는것을 다시 복원하는 것이다.
recursion이 데이터를 변경할 때는 매우 조심해야한다.
호출 전후에 데이터가 변경되지 않고 유지되도록 하는게 좋다.

 

레퍼런스

• [권오흠 알고리즘] 제2-5강 순열(permutation)