꽤 다양하게 응용할 수 있는 4가지 알고리즘의 코드를 자바로 한번 구현해보았다. 모두 생각보다 직접 떠올리기 쉽지 않다.

만약 기억하기 어렵다면 한가지만 떠올리자. DFS + 재귀로 구현 가능하다.
순열은 해당 자리에 어떤 원소를 넣을까를 고민한다.
조합은 해당 원소를 뽑을까 말까를 고민한다.

순열

두 구현방식 모두 재귀를 사용하지만 장단점이 있다.

구현 1. swap (빠른 방법)

구글링 해보니 해당 방법을 좀 더 많이 사용하는 것으로 보인다. 첫 번째 자리부터 값을 고정하고 나머지를 swap해가며 탐색한다.

주의할 점: 사전식 순서를 제공하지 않는다는 점.
시간복잡도 : O(n!/(n-r)! * r) = O(P(n, r) * r)

트리를 보면 노드마다 swap연산이 한번씩 일어나며 각 depth마다 n, n(n-1), n(n-1)(n-2)... 식으로 늘어난다. Swap은 O(1)이므로 최종 시간복잡도는 위와 같다.

public class Main {
    public static void permutation(int[] arr, int depth, int r) {
        if (depth == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = depth; i < arr.length; i++) {
            swap(arr, i, depth);
            permutation(arr, depth + 1, r);
            swap(arr, i, depth);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

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

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

구현 2. visited를 활용한 DFS (사전식 순서 방법)

DFS와 visited로 이미 사용된 수를 구별해 순서대로 탐색한다. 사전식 순서를 제공하지만 swap방식보다 불필요한 검사가 진행되어 느리다.

시간복잡도 : O(n!/(n-r)! * rn) = O(P(n, r) * rn)

swap방식에서 swap 연산이 노드별로 O(1)로 한번씩 일어났다면 O(n)만큼 미방문 노드를 탐색하는 시간이 걸려 최종적으로 *n만큼 시간이 더 든다.

public class Main {
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r) {
        if (depth == r) {
            for (int num : out) System.out.print(num + " ");
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, out, visited, depth + 1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
}

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int[] out	결과를 담을 배열(고정)
boolean[] visited	선택된 원소를 기록할 배열(고정)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

중복순열

재귀로 구현 가능하며 쉽게 생각 가능하다.

시간복잡도는 : O(n^r * r) = O(Pi(n, r) * r)

public class Main {
    public static void permutation(int[] arr, int[] out, int depth, int r) {
        if (depth == r) {
            for (int i :out) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            out[depth] = arr[i];
            permutation(arr, out, depth + 1, r);
        }
    }

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

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int[] out	결과를 담을 배열(고정)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

조합

조합의 구현도 재귀구조로 가능하다.
다른 블로그를 참고하면 점화식을 이용한 풀이도 있지만 속도면에서 부족함이 없고 떠올리기 쉽다고 생각하는 방법을 가져왔다.

구현 1. DFS를 이용한 풀이

인덱스 순서대로 원소를 나열하고 첫번째 원소부터 뽑을지 안뽑을지를 결정하다가 r개가 뽑히면 반환하는 방식으로 찾아볼 수 있다.

시간복잡도 : O(2^n)

포화이진트리의 노드개수 공식에 의해서 r을 곱할 필요는 없다.

public class Main {
    public static void combination(int[] arr, int[] out, int start, int depth, int r) {
        if (depth == r) {
            for (int i :out) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < arr.length; i++) {
            out[depth] = arr[i];
            combination(arr, out, i + 1, depth + 1, r);
        }
    }

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

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int[] out	결과를 담을 배열(고정)
int start	앞으로 결정해야할 원소들 중 첫번째 원소의 인덱스(변수)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

구현 2. 백트레킹(더 빠른 방법)

구현 1은 느리다. 이는 모든 뽑거나 안뽑는 경우를 모두 따져서 r개만큼 원소를 뽑기에 부족한 불필요한 경우도 탐색하기 때문이다. 이를 백트레킹 기법을 활용해 잘 조절해주면 원하는 경우의 수만 추출 가능하다.

구현 1과 완벽히 동일하지만, for문의 조건이 추가되었다.

시간복잡도 : O(n!/(n-r)!r! * r) = O(C(n, r) * r)

public class Main {
    public static void combination(int[] arr, int[] out, int start, int depth, int r) {
        if (depth == r) {
            for (int i :out) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < arr.length - r + depth + 1; i++) {
            out[depth] = arr[i];
            combination(arr, out, i + 1, depth + 1, r);
        }
    }

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

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int[] out	결과를 담을 배열(고정)
int start	앞으로 결정해야할 원소들 중 첫번째 원소의 인덱스(변수)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

중복조합

중복조합은 조합을 구현했다면 상당히 간단히 구현할 수 있다. start를 + 1 로 재귀호출 하지 않고 start 그대로 한번 더 뽑을 수 있도록 한다.

시간복잡도 : O((n+r-1)!/(n-1)!r! * r) = O(H(n, r) * r) = O(C(n+r-1, r) * r)

public class Main {
    public static void combination(int[] arr, int[] out, int start, int depth, int r) {
        if (depth == r) {
            for (int i :out) {
                System.out.print(i + " ");
            }
            System.out.println();
            return;
        }

        for (int i = start; i < arr.length; i++) {
            out[depth] = arr[i];
            combination(arr, out, i, depth + 1, r);
        }
    }

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

인수명	설명
int[] arr	순열로 정렬할 원소들 (고정)
int[] out	결과를 담을 배열(고정)
int start	앞으로 결정해야할 원소들 중 첫번째 원소의 인덱스(변수)
int depth	선택된 원소 개수 = 재귀의 깊이(변수)
int r	선택할 원소의 총 개수(고정)

참고

https://bcp0109.tistory.com/14