순열(permutation) 알고리즘

순열(permutation)

순열이란 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다.

예를들어,  집합의 원소가 {A, B, C} 일때, 3개의 원소를 모두 사용하여 순서를 고려해 나열하는 경우의 수는

A B C, A C B, B A C, B C A, C B A, C A B로 총 6가지 경우가 나오게 됩니다.

순열 알고리즘

순열의 모든 경우를 빼먹지 않고 고려하기 위해서는 아래와 같은 로직으로 찾아갑니다.

1. 0번째 인덱스 원소를, 0번째 부터 n-1번째까지 위치를 바꿉니다. ( A B C를 기준으로 이 과정을 진행하면 A B C, B A C, C B A 가 됩니다.)
2. 1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를, 1번째 부터 n-1번째까지 위치를 바꿉니다.
3. 이러한 과정을 n-1번 진행합니다.

그림으로 도식화 하면 아래와 같습니다.

이미지 출처 : https://www.geeksforgeeks.org/wp-content/uploads/NewPermutation.gif

이미지의 가장 아래 단 6가지 경우가 위에서 언급한 순열의 모든 경우의 수 입니다. (처음과 중간 과정은 구하는 과정일 뿐입니다.)

만약 n개에서 r개만을 고르는 경우를 알고 싶다면 n-1번째가 아닌 r번만 반복하고, 순서의 0번째 부터 r번째 까지만 확인하면 됩니다.

코드로 구현하기 (java)

재귀적으로 구현한다면 코드로 구현하기 어렵지는 않습니다. 주의할 점은 원소의 위치를 바꾼 후에 같은 단계(depth)내에서는, 바꾸기 전의 순서대로 되돌린 후 진행해야 합니다.

public class Permutation {
    public static void main(String[] args) {
        char[] chars = {'a', 'b', 'c', 'd'};
        permutation(chars, 0, 3);
    }

    static void permutation(char[] chars, int depth, int r) { 
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(chars[i] + "\t");
            }
            System.out.println();
            return;
        }

        for (int i = depth; i < chars.length; i++) {
            char tmp = chars[depth];
            chars[depth] = chars[i];
            chars[i] = tmp;

            permutation(chars, depth + 1, r);

            //스왑한거 다시 되돌리기
            chars[i] = chars[depth];
            chars[depth] = tmp;
        }
    }
}