Algorithm - 순열, 조합, 중복순열, 중복조합 (Java)

 

 

코딩테스트 문제를 풀다보면 순열, 조합 혹은 중복순열, 중복조합을 활용해야 하는 경우가 종종 있다. 하나하나 정리해보자.

 

 

 

1. 순열

 

 

순열은 주어진 n개의 원소에서 순서에 상관있게 r 개를 나열하는것을 말합니다.

 

예로 1, 2, 3, 4 에서 2개의 원소를 뽑아 나열하는 경우

 

1, 3

3, 1

 

은 다른 경우가 됩니다. 두 경우 모두 1과 3으로만 이루어져 있지만 순서가 다르기 때문에 다른 경우로 봅니다.

 

경우의 수는 총 nPr = n! / (n - r)!

 

 

---

구현 방식

 

백트래킹 방식으로 구현 가능하며 한 번 방문한 요소는 다시 방문할 필요가 없으므로 visit 배열을 활용해 방문하지 않은 원소 위주로 탐색합니다.

 

depth를 1씩 늘려가며 이전에 방문하지 않은 요소를 정답 기록용 배열 (int[] rec) 에 저장한다.

 

depth가 r과 같은 값이 되면 정답 기록용 배열 (int[] rec) 출력.

 

import java.util.Arrays;

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

        int n = arr.length;
        int r = 2;

        permutation(arr, new int[r], new boolean[n], 0, r);
    }
	// 4개의 원소에서 2개를 뽑아 순열로 나열
    public static void permutation(int [] arr, int[] rec, boolean[] visit, int depth, int r) {
        if (depth == r) {
            System.out.println(Arrays.toString(rec));
            return;
        }

        for (int i = 0 ; i < arr.length ; i++) {
            if (!visit[i]) {
                visit[i] = true;
                rec[depth] = arr[i];
                permutation(arr, rec, visit, depth + 1, r);
                visit[i] = false;
            }
        }
    }
}

---

결과

 

 

2. 조합

 

 

조합은 주어진 n개의 원소에서 순서에 상관없이 r 개를 나열하는것을 말합니다.

 

예로 1, 2, 3, 4 에서 2개의 원소를 뽑는 경우

 

1, 3

3, 1

 

은 같은 경우가 됩니다. 두 경우 모두 1과 3으로만 이루어져 있기 때문에 같은 경우로 봅니다.

 

경우의 수는 총 nCr = n! / (n - r)! * r!

 

---

구현 방식

 

백트래킹 방식으로 구현 가능하며 한 요소를 방문할 경우 해당 요소와 이전 요소는 방문할 일이 없으므로 해당 요소 이후 요소 (i + 1) 만을 탐색합니다.

 

다음 재귀 호출 시 매개변수 start에 i + 1를 주어 구현할 수 있습니다.

 

 

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

        int r = 2;

        combination(arr, new int[r], 0, r, 0);
    }

    static void combination(int [] arr, int [] rec, int start, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(rec));
            return;
        }

        for (int i = start ; i < arr.length ; i++) {
            rec[depth] = arr[i];
            combination(arr, rec, i + 1, r, depth + 1);
        }
    }
}

---

결과

 

 

3. 중복 순열

 

 

중복순열은 순열과 비슷하나 n개의 원소 중에서 r개의 원소를 중복을 허용하면서 나열하는 것입니다.

예로 1, 2, 3, 4 에서 2개를 뽑아 중복순열을 만들면

 

1 1

1 2

1 3

1 4

2 1

2 2

...

4 3

4 4

 

가 나오게 됩니다.

 

경우의 수는 n^r 

 

---

구현 방식

 

순열 코드에서 방문을 기록하는 boolean 배열을 사용하는 이유는 중복을 막기 위함입니다.

중복순열은 순열 코드에서 방문 관련 코드만 제거하면 구현됩니다.

 

import java.util.Arrays;

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

        int n = arr.length;
        int r = 2;

        dup_permutation(arr, new int[r], 0, r);
    }

    public static void dup_permutation(int [] arr, int [] rec, int depth, int r) {
        if (depth == r) {
            System.out.println(Arrays.toString(rec));
            return;
        }

        for (int i = 0 ; i < arr.length ; i++) {
            rec[depth] = arr[i];
            dup_permutation(arr, rec,depth + 1, r);
        }
    }
}

---

결과

 

 

4. 중복 조합

 

 

중복조합또한 조합과 다른점은 원소의 중복을 허락하느냐 허락하지 않느냐 차이 뿐입니다.

 

경우의 수는 nHr 로

 

nHr = n + r - 1 C r

 

예 : 4H2 = 5C2

 

---

구현 방식

 

조합 코드에서는 방문한 요소와 방문한 요소 이전 요소들은 더 이상 볼 필요가 없어지므로 start의 다음 인자로 i + 1를 전달했으나 중복조합은 i + 1가 아닌 i 값만 전달하여 중복 선택 되도록 구현하면 됩니다.

 

import java.util.Arrays;

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

        int n = arr.length;
        int r = 2;

        dup_combination(arr, new int[r], 0, 0);
    }

    public static void dup_combination(int [] arr, int[] rec, int start, int r) {
        if (r == rec.length) {
            System.out.println(Arrays.toString(rec));
            return;
        }

        for (int i = start ; i < arr.length ; i++) {
            rec[r] = arr[i];
            dup_combination(arr, rec, i, r + 1);
        }
    }
}

---

결과