순열과 조합

순열과 조합

순열과 조합은 알고리즘 문제에서 자주 등장하는 개념으로, 문제 속의 문제로 나오거나 약간 변형하는 식으로 자주 나오기 때문에 기본적으로 알고 있어야 한다. 제대로 내가 알고 있는지 확인하고 똑바로 머리에 새겨놓기 위해 포스팅으로 정리한다.

---

순열 (Permutation)

• 순서가 있는 n개의 원소를 가능한 다른 순서로 뒤섞는 연산
• 전체 경우의 수는 n!와 같다.

구현

순열 연산은 재귀적으로 구현할 수 있다.

• depth를 통해 순열에 저장한 원소 개수를 체크한다.
• visited를 통해 한 원소를 한 번만 사용할 수 있도록 체크한다.
• result에 완성된 순열을 저장한다.

실제 문제에서는 종료나 다른 조건들을 문제에 맞게 변형해서 응용하면 된다.

import java.util.Arrays;

public class Permutation {

    public static void main(String[] args) {
        Permutation permutation = new Permutation(3, 3, new int[]{1, 2, 3});
        permutation.doPermutation();
    }

    public Permutation(int n, int r, int[] arr) {
        this.n = n;
        this.r = r;
        this.arr = arr;
    }

    private int n;
    private int r;
    private int[] arr;

    public void doPermutation() {
        int[] result = new int[this.r];
        boolean[] visited = new boolean[this.n];
        dfs(result, visited, 0);
    }

    private void dfs(int[] result, boolean[] visited, int depth) {
        if (depth == r) {
            printResult(result);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = arr[i];
                dfs(result, visited, depth + 1);
                visited[i] = false;
                result[depth] = 0;
            }
        }
    }

    private void printResult(int[] result) {
        System.out.println(Arrays.toString(result));
    }
}

수행결과

예) 3P3

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

---

조합 (Combination)

• 순서가 없는 n개의 원소 중 r개를 선택하는 연산
• 전체 경우의 수는 n! / (n-r)!r!와 같다.

구현

조합은 위의 순열 코드와 비슷하지만 start 인덱스를 체크한다는 점에 차이가 있다. 순열은 순서가 다르면 다른 결과로 보지만 조합은 순서 상관없이 원소의 조합만 보기 때문이다. 따라서 start 인덱스를 지정해서 그 인덱스 이후의 원소부터 탐색하도록 했고, 이를 통해 순서만 다른 같은 집합을 중복으로 찾지 않을 수 있다.

import java.util.Arrays;

public class Combination {

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

    public Combination(int n, int r, int[] arr) {
        this.n = n;
        this.r = r;
        this.arr = arr;
    }

    private int n;
    private int r;
    private int[] arr;

    public void doCombination() {
        int[] result = new int[this.r];
        boolean[] visited = new boolean[this.n];
        dfs(result, visited, 0, 0);
    }

    private void dfs(int[] result, boolean[] visited, int start, int depth) {
        if (depth == r) {
            printResult(result);
            return;
        }

        for (int i = start; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = arr[i];
                dfs(result, visited, i + 1, depth + 1);
                visited[i] = false;
                result[depth] = 0;
            }
        }
    }

    private void printResult(int[] result) {
        System.out.println(Arrays.toString(result));
    }
}

수행결과

예) 3C1

[1]
[2]
[3]

예) 3C2

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

예) 3C3

[1, 2, 3]