[알고리즘] 순조부(순열/조합/부분집합)

1. 순열

• n개의 원소에서 r개를 중복을 허용하지 않고 선택해서 순서대로 나열하는 것을 말하며 nPr이라고 표기
• 순열의 순서는 유의미!!  즉, 순서가 바뀐다면 다른 순열을 뜻함

순열의 시간복잡도

순열은 nPr로 표기를 하며 n개 중 r개를 뽑는 것을 말한다. 식으로 표현하면
nPr = n (n-1) ... (n-r+1)
nPn = n!
➡️ 따라서 순열의 시간복잡도는 O(N!)

• O(N!)이라서 속도 측면에서는 느림

• 정의 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열(순서있게)하는 것 

순열은 간단하게 말해 순서가 있는 집합이라 표현할 수 있습니다.

예를 들어 {1, 2, 3} 과 {2, 1, 3}은 내용물은 같지만 순서가 다르죠

이 경우 순열에서는 두 집합은 다른 집합입니다.

• 표현
  • nPr
    • nPr = n * (n-1) * (n-2) * … * (n-r+1)
    • nPn = n!
  • 중복순열은 nΠr로 표시
    • n^r

• 순열 사용 방식
  • 일반 재귀
  • 비트마스킹
  • Next Permutation(NP, 넥퍼)
    • 현 순열에서 사전 순으로 다음 순열 생성
    • 배열을 오름차순으로 정렬한 후 시작

import java.util.ArrayList;
import java.util.List;

public class Permutation {
    public static void main(String[] args) {
        List<Integer> data = List.of(1, 2, 3);
        List<List<Integer>> result = new ArrayList<>();
        permute(data, new ArrayList<>(), result);
        
        System.out.println("순열:");
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }

    private static void permute(List<Integer> data, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == data.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < data.size(); i++) {
            if (current.contains(data.get(i))) continue; // 중복 방지
            current.add(data.get(i));
            permute(data, current, result);
            current.remove(current.size() - 1);
        }
    }
}

---

2. 조합

 

• 정의 - 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

중복 조합은 순열과 비슷하지만 다르게 순서가 없는 집합입니다.

예를 들어 {1, 2, 3} 과 {2, 1, 3}은 같은 집합으로 취급합니다.

• 표현
  • nCr
    • nCr = n! / (n-r)!r!
    • nCr = n-1Cr-1 + n-1Cr
    • nC0 = 1
  • 중복조합은 nHr로 표시
    • n+r-1Cr

• 조합 사용 방식
  • 일반 재귀
  • Next Permutation(NP, 넥퍼)
    • n크기의 배열에 r개를 뒤쪽부터 1로 채우고 넥퍼를 진행하여 나온 결과를 기존 배열의 위치와 비교하면 조합

import java.util.ArrayList;
import java.util.List;

public class Combination {
    public static void main(String[] args) {
        List<Integer> data = List.of(1, 2, 3);
        List<List<Integer>> result = new ArrayList<>();
        int r = 2; // 조합에서 선택할 원소의 개수
        combine(data, r, 0, new ArrayList<>(), result);
        
        System.out.println("\n조합:");
        for (List<Integer> comb : result) {
            System.out.println(comb);
        }
    }

    private static void combine(List<Integer> data, int r, int start, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == r) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < data.size(); i++) {
            current.add(data.get(i));
            combine(data, r, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

---

3. 부분집합

• 정의 - 집합에 포함된 원소들을 선택하는 것

부분 집합은 공집합을 포함하여 해당 집합에서 선택할 수 있는 모든 경우의 수를 나타냅니다.

예를 들어 {1, 2, 3}의 부분 집합은 {∅}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 입니다.

• 부분 집합의 수
  • 공집합 포함하여 2^n

• 부분 집합 표현 방식
  • 일반 재귀
  • 바이너리 카운팅

고려 사항

• 순열은 n의 수가 10보다 클 경우 순열 문제가 아닐 가능성이 높음
  • 순열의 시간복잡도 n!
• 조합은 n=30, r=15일 경우 약 1억 5천
• 부분 집합은 n이 30일 경우
  • 2^20은 약 100만, 2^30은 약 10억

Java 기준 시간복잡도는 1억에 1초로 생각하시면 됩니다.

 

import java.util.ArrayList;
import java.util.List;

public class Subset {
    public static void main(String[] args) {
        List<Integer> data = List.of(1, 2, 3);
        List<List<Integer>> result = new ArrayList<>();
        generateSubsets(data, 0, new ArrayList<>(), result);
        
        System.out.println("\n부분집합:");
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }

    private static void generateSubsets(List<Integer> data, int index, List<Integer> current, List<List<Integer>> result) {
        if (index == data.size()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // 현재 원소를 포함하지 않는 부분집합
        generateSubsets(data, index + 1, current, result);
        
        // 현재 원소를 포함하는 부분집합
        current.add(data.get(index));
        generateSubsets(data, index + 1, current, result);
        current.remove(current.size() - 1);
    }
}

---

참조

https://ghs4593.tistory.com/7

순조부 1 - 순열, 조합, 부분 집합

https://blackvill.tistory.com/244

[알고리즘] 순열 vs 조합 vs 부분 집합 (순조부)

https://velog.io/@rkdalstj4505/%EC%88%9C%EC%A1%B0%EB%B6%80%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9

[알고리즘]순열/조합/부분집합