[알고리즘] 순열과 조합

1. 순열 Permutation

• 길이가 n개인 배열에서 r개의 요소를 차례로 뽑아 새로운 배열을 만들었을 때 가능한 모든 배열(중복제외)
  → 순열, 중복 순열, 조합, 중복조합 모두 n개에서 r개를 뽑는다는 점에서 동일
• 순열의 정의에서는 정렬.  순서가 있다는 것이 특징

public class AlgorithmStudy {
    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);
    }
}

→ 결과 :  1 2 / 1 3 / 2 1 / 2 3 / 3 1 / 3 2

 

2. 중복 순열

• 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수
• 순서가 있다는 점에서 순열과 동일. 같은 원소를 중복해서 뽑을 수 있다는 점에서 차이
  → 순열 코드에서 중복방지를 위해 사용했던 visited 부분을 제거하면 된다.

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, 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++){
            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);
    }
}

→ 결과 :  1 1 / 1 2 / 1 3 /  2 1 / 2 2 / 2 3 / 3 1 / 3 2 / 3 3

---

 

3. 조합 Combination

• 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수(중복제외)
  →[1, 2] 와 [2, 1]을 같은 것으로 취급 ▷ 이 경우 [1, 2]만 카운팅
• 순서 상관이 없고, 중복도 없기 때문에 선택된 원소를 따로 저장하지 않고, 
  원소들과 visited만 이용하여 방문한 원소들을 순서대로 확인하면 곧 선택된 조합

public class AlgorithmStudy {
    public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(visited[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }

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

→ 결과 : 1 2 / 1 3 / 2 3

 

4. 중복 조합

• 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
• 순서 없이 뽑는 조합과 동일하지만, 중복이 가능하다는 점에서 차이(즉, 이미 뽑은 것을 또 뽑을 수 있음)
  → 조합 코드에서 중복방지를 위해사용했던 visited 부분을 제거하면 된다.
  → 중복이 가능하므로 선택한 원소를 저장하는 배열 필요

public class AlgorithmStudy {
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            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);
    }
}

결과 → 1 1 / 1 2 / 1 3 / 2 2 / 2 3 / 3 3

 

 

참고) https://minhamina.tistory.com/37

[Java] 순열 Permutation

 

참고) https://bcp0109.tistory.com/14

순열 Permutation (Java)