순열, 중복순열, 조합, 중복 조합 알고리즘

순열

: 순열 알고리즘은 전체 배열에서 순서에 상관 있게 r개를 뽑는 것이다.

즉, 1,2와 2,1을 다른 경우로 보는 것이다. 따라서 dfs를 수행할 때 arr을 항상 0 인덱스부터 돌면서 수행시켜줘야 한다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,5};
        int r = 2;
        permutation(arr, r, 0, new boolean[arr.length], new int[r]);
    }
    static void permutation(int[] arr, int r, int depth, boolean[] visited, int[] result) {
        if (depth == r) {
            for (int n : result) System.out.print(n + " ");
            System.out.println();
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = arr[i];
                permutation(arr, r, depth+1, visited, result);
                visited[i] = false;
            }
        }
    }
}

 

중복 순열

: 중복 순열은 똑같은 수를 여러 번 뽑아도 되는 순열이다.

즉, 1,1 2,2 같은 경우가 가능하다. 따라서 순열 알고리즘에서 visited를 체크하는 부분을 삭제하면 된다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,5};
        int r = 2;
        permutation(arr, r, 0, new boolean[arr.length], new int[r]);
    }
    static void permutation(int[] arr, int r, int depth, boolean[] visited, int[] result) {
        if (depth == r) {
            for (int n : result) System.out.print(n + " ");
            System.out.println();
            return;
        }
        for (int i = 0; i < arr.length; i++) {
                result[depth] = arr[i];
                permutation(arr, r, depth+1, visited, result);
        }
    }
}

출력

1 5 
2 1 
2 2 
2 5 
5 1 
5 2 
5 5 

 

조합

: 조합은 순열과 다르게 순서에 상관없이 r개를 뽑는 알고리즘이다.  따라서 1,2 와 2,1을 같은 경우로 본다.

조합의 경우는 순열 코드에서 idx 파라미터를 추가해 자신보다 큰 수만 뽑을 수 있도록 수정해주면 된다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,5};
        int r = 2;
        combination(arr, r, 0, new boolean[arr.length], new int[r], 0);
    }
    static void combination(int[] arr, int r, int depth, boolean[] visited, int[] result, int idx) {
        if (depth == r) {
            for (int n : result) System.out.print(n + " ");
            System.out.println();
            return;
        }
        for (int i = idx; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = arr[i];
                combination(arr, r, depth + 1, visited, result, i);
                visited[i] = false;
            }
        }
    }
}

중복 조합

: 중복 조합도 중복 순열과 마찬가지로 1,1  2,2를 허용한다.

따라서 visited를 체크하는 부분만 없애주면 된다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {1,2,5};
        int r = 2;
        combination(arr, r, 0, new boolean[arr.length], new int[r], 0);
    }
    static void combination(int[] arr, int r, int depth, boolean[] visited, int[] result, int idx) {
        if (depth == r) {
            for (int n : result) System.out.print(n + " ");
            System.out.println();
            return;
        }
        for (int i = idx; i < arr.length; i++) {
                result[depth] = arr[i];
                combination(arr, r, depth + 1, visited, result, i);
        }
    }
}

출력

1 1 
1 2 
1 5 
2 2 
2 5 
5 5