[Algorithm/Java] 순열과 조합

순열이란?

서로 다른 n개 중 r개를 뽑아서 나열한 것

조합이란?

서로 다른 n개 중 r개를 순서 없이 골라낸 것

즉, AB != AB와 같이 순서가 의미 있으면 순열이고,
AB == BA와 같이 순서가 의미 없으면 조합!
그리고 순열, 조합에서 중복을 허용하면 중복 순열, 중복 조합이라고 부른다.

코드로 구현해보자! (☞ﾟヮﾟ)☞💻

공통 로직

public class 순열 {
    private static int n, m;
    private static int[] arr; // 원소를 저장할 배열
    private static boolean[] visited; // 중복을 제거하기 위한 방문 처리

    public static void main(String[] args) {
        n = 4;
        m = 2;
        arr = new int[m];
        visited = new boolean[n + 1];
        permutation(0);
    }
    
}

순열

	// 순열
    private static void permutation(int cnt) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[cnt] = i;
                permutation(cnt + 1);
                visited[i] = false;
            }
        }
    }
    
    // 중복 순열 - 중복 제거하는 visited를 쓰지 않음
    private static void repeatedPermutation(int cnt) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            arr[cnt] = i;
            permutation(cnt + 1);
        }
    }

결과

순열

[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]

중복 순열

[1, 1] - 중복 존재
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]

조합

	// 조합
    private static void combination(int cnt, int start) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i + 1); // 오름차순으로 구하면 중복 체크하지 않아도 됨
        }
    }

    // 중복 조합
    private static void repeatedCombination(int cnt, int start) {
        if (cnt == m) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr[cnt] = i;
            combination(cnt + 1, i); // 중복 허용하니까 비내림차순
        }
    }

결과

조합

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

중복 조합

[1, 1] - 중복 존재
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[2, 4]
[3, 3]
[3, 4]
[4, 4]

정리!

[1, 2] 와 [2, 1]이 다르면 순열!
비유하자면 반에서 반장, 부반장을 뽑는 것과 같다.
[1, 2] 와 [2, 1]이 같으면 조합!
비유하자면 반에서 당번 2명을 뽑는 것과 같다. 두명의 순서가 상관없음