순열, 조합

순열

---

서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){

        if(depth == r){ //(3)
            for(int num : out)
                System.out.print(num);
            return;
        }

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

    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);
    }
}

파라미터

• arr : 순열의 대상이 되는 배열
• out : 순열의 결과를 담는 배열
• visited : 이미 방문한 인덱스를 체크하는 배열
• dpeth : 현재 몇 번째 원소를 정열중인지 나타내는 수
• r : nCr에서의 r, 즉 뽑아야 하는 수

로직

• (1) : 순열의 대상이 되는 배열(arr)의 길이만큼 for문을 돌면서 방문하지 않은 인덱스면 visited[i]를 true로 바꿔주고, 순열의 결과를 담는 배열(out)에 해당 인덱스의 값을 써준다.
• (2) : depth + 1해서 재귀로 permutation 메서드를 호출한다.
• (3) : depth와 뽑아야 하는 수가 같다면 그대로 out배열을 출력 후 해당 재귀는 종료한다.
• (4) : visited[i]를 다시 false로 바꿔주어 arr배열에서 다음 인덱스를 out 배열에 넣을 수 있게 한다.

 

 

 

조합

---

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

배열을 처음부터 마지막까지 돌며

1. 현재 인덱스를 선택하는 경우
2. 현재 인덱스를 선택하지 않는 경우

백트래킹

static void combination(int[] arr, boolean[] visited, int start, 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;
        }

        for(int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
}

start 변수를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보이다.

 

재귀 이용

static void comb(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;
        comb(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        comb(arr, visited, depth + 1, n, r);
}

depth 변수는 현재 인덱스라고 생각할 수 있다.

현재 인덱스를 뽑는다면 visited[depth] = true

뽑지 않는다면 visited[depth] = false

이전에 본 값들은 더이상 고려 대상이 아니기 때문에 depth 는 무조건 1씩 증가한다.

depth == n이 되면 모든 인덱스를 다 보았으므로 재귀를 종료한다.