Java 순열과 조합

1, 2, 3, 4를 이용하여 세 자리 자연수 만들기 (순서 O, 중복 X)

 

Swap 함수를 이용한 순열

swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법입니다.

배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 합니다.

depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고

depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행합니다.

 

swap을 이용한 재귀 호출

public class SwapPermutation {
    // depth: 각 자릿수
    void permutation(int[] arr, int depth, int n, 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 < n; i++) {
            swap(arr, depth, i);
            permutation(arr, depth + 1, n , r);
            swap(arr, depth, i);
        }
    }

    // depth: 몇 번째 자릿 수
    // idx: 바꿀 위치
    void swap(int[] arr, int depth, int idx) {
        int tmp = arr[depth];
        arr[depth] = arr[idx];
        arr[idx] = tmp;
    }

    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};

        SwapPermutation p = new SwapPermutation();
        // n은 숫자 총 개수
        // 3은 몇 자리 자연수 인지
        // depth는 각 자릿수
        p.permutation(arr, 0, 4, 3);
    }
}

Visited boolean 배열을 이용한 순열

1, 2, 3

1, 2, 4

1, 3, 2 와 같이 순서가 제대로 보장된 방법입니다.

 

arr	r 개를 뽑기 위한 n 개의 값
out	뽑힌 r 개의 값
visited	중복해서 뽑지 않기 위해 체크하는 값

깊이 우선 탐색(DFS)을 이용하여 모든 인덱스를 방문하여 out 에 값을 넣습니다.

이미 들어간 값은 visited 값을 true 로 바꾸어 중복하여 넣지 않도록 합니다.

depth 값은 out 에 들어간 숫자의 길이라고 생각하시면 됩니다.

depth 의 값이 r 만큼 되면 output 에 들어있는 값을 출력하면 됩니다.

주의) out[depth] 자릿수의 값을 arr[i] 번째 자리의 값으로 변경하여 합니다.

 

visited를 이용한 깊이 우선 탐색 재귀 호출

public class VisitedPermutation {
    void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
        if (depth == r) {
            System.out.println(Arrays.toString(out));
            return;
        }

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

    public static void main(String[] args) {
//      Test code
        int n = 4;
        int r = 3;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];
        int[] out = new int[r];

        VisitedPermutation p = new VisitedPermutation();
        p.permutation(arr, 0, n, r, visited, out);
    }
}

Visited boolean을 이용한 재귀 조합

몇 개를 뽑는지 결정하는 r이 0에 도달하는 조건과 depth가 최대 자리 수에 도달하는 조건 모두에서

리턴이 필요합니다.

public class VisitedCombination {
    void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) return;

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
    }
    
    public static void main(String[] args) {
//      Test code
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = {false, false, false, false};

        VisitedCombination c = new VisitedCombination();
        c.combination(arr, visited, 0, 4, 3);
    }
}

 

Visited boolean을 이용한 백트래킹 조합

아래 블로그를 통하여 백트래킹을 활용한 조합 방법을 찾을 수 있습니다.

https://bcp0109.tistory.com/15

조합 Combination (Java)