순열, 조합, 부분집합

순열(Permutation)

1. 정의

순열은 주어진 n개의 원소 중 r개를 선택해 순서를 고려하여 나열하는 것을 의미
같은 원소 집합이라도 순서가 다르면 다른 경우로 취급된다.

2. 수학적 표현

P(n,r)=n!(n−r)!

• n! : n개의 원소를 전부 나열하는 경우의 수
• (n-r)! : 선택하지 않은 원소들의 순서를 제거하기 위한 나눗셈

즉, 첫 번째 원소를 n가지 중에서 선택하고, 두 번째를 n-1가지 중에서 선택하는 과정을 r번 반복하는 방식

3. 예시

n = 4, r = 2일 때:

P(4,2)=4!(4−2)!=242=12P(4,2)=\frac{4!}{(4-2)!}=\frac{24}{2}=12

가능한 순열:

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

 

4. 순열 트리(의사결정 트리)

        []
    /    |    \
  [1]   [2]   [3]
 /   \  /   \  /   \
[1,2][1,3][2,1][2,3][3,1][3,2]

• 각 단계에서 숫자를 하나 선택 → 탐색
• 탐색 종료 후 상태를 되돌려 다른 경우 탐색 (Backtracking)

5. 코드 예시

(1) 1~n 범위 숫자

import java.util.*;

public class PermutationGenerator {
    public static List<List<Integer>> permute(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[n + 1];
        backtrack(n, r, new ArrayList<>(), visited, ans);
        return ans;
    }

    private static void backtrack(int n, int r, List<Integer> curr,
                                   boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                curr.add(i);
                visited[i] = true;
                backtrack(n, r, curr, visited, ans);
                curr.remove(curr.size() - 1);
                visited[i] = false; // 상태 되돌리기
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(permute(4, 2));
    }
}

(2) 임의 배열

import java.util.*;

public class PermutationWithArray {
    public static List<List<Integer>> permute(int[] nums, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        backtrack(r, new ArrayList<>(), nums, visited, ans);
        return ans;
    }

    private static void backtrack(int r, List<Integer> curr, int[] nums,
                                   boolean[] visited, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                curr.add(nums[i]);
                visited[i] = true;
                backtrack(r, curr, nums, visited, ans);
                curr.remove(curr.size() - 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums, 2));
    }
}

 

조합(Combination)

1. 정의

조합은 주어진 n개의 원소 중 r개를 선택하되, 순서를 고려하지 않는 경우
같은 원소라면 순서가 달라도 같은 경우로 간주

2. 수학적 표현

C(n,r)=n!r!(n−r)!

• 순열 결과에서 중복되는 순서를 제거하기 위해 r!로 나눕니다.

3. 예시

n=4, r=2일 때:

C(4,2)=4!2!(4−2)!=244=6C(4,2)=\frac{4!}{2!(4-2)!}=\frac{24}{4}=6

가능한 조합:

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

 

4. 코드 예시

import java.util.*;

public class Combination {
    public static List<List<Integer>> combine(int n, int r) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, r, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr,
                                  int n, int r, List<List<Integer>> ans) {
        if (curr.size() == r) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = start; i <= n; i++) {
            curr.add(i);
            backtrack(i + 1, curr, n, r, ans); // 다음 숫자는 현재보다 큰 것만
            curr.remove(curr.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
    }
}

 

부분집합(Subset)

1. 정의

부분집합은 주어진 집합에서 원소를 선택할 수도, 하지 않을 수도 있는 모든 경우의 집합
공집합과 자기 자신도 포함된다.

2. 개수

각 원소마다 선택 / 미선택 두 가지 경우가 있으므로: 부분집합개수=2n부분집합 개수 = 2^n

3. 예시

{a, b, c} → 부분집합 8개:

[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]

 

4. 코드 예시

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, new ArrayList<>(), n, ans);
        return ans;
    }

    private static void backtrack(int start, List<Integer> curr,
                                  int n, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(curr)); // 현재 부분집합 추가
        for (int i = start; i <= n; i++) {
            curr.add(i);
            backtrack(i + 1, curr, n, ans);
            curr.remove(curr.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(3));
    }
}