[Java] 순열/조합/부분집합

💡순열(Permutation)

: 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을
순열(permutation)이라고 한다. (나무위키)

//nPr 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        input = new int[N];
        numbers = new int[R];
        isSelected = new boolean[N]; // 방문 여부를 체크하기 위함

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        permutation(0);
    }

    private static void permutation(int cnt) {
        if(cnt == R) { // R개의 원소를 다 뽑았다면 return
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for(int i=0; i<N; ++i) {
             //뽑으려는 수가 사용 됐다면
            if(isSelected[i]) continue;

            // 뽑으려는 수가 사용되지 않았다면 

            // 배열에 넣어줌
            numbers[cnt] = input[i];
            // 사용처리 true
            isSelected[i] = true;
            permutation(cnt+1);
            // R개의 원소 생성 후 사용처리 다시 해제 
            isSelected[i] = false;
        }
    }

🚨 주요 포인트

boolean타입의 isSelected 배열을 통해서 원소를 뽑았는지 안뽑았는지 체크하는 것이 포인트다

중복 순열의 경우(1,1,1), (1,2,1),(2,1,1)

isSelected 배열을 통해 원소 체크를 하지 않아도 된다

---

💡조합(Combination)

: 서로 다른 n개의 원소를 가지는 어떤 집합 (사실, 집합은 서로 다른 원소의 모임으로 정의된다.)

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        R = sc.nextInt();
        input = new int[N];
        numbers = new int[R];

        for (int i = 0; i < N; i++) {
                input[i] = sc.nextInt();
        }
        combination(0,0);
    }

    private static void combination(int cnt,int start) {
        if(cnt == R) { //R개의 원소를 다 뽑았다면 
                System.out.println(Arrays.toString(numbers));
                return;
        }
        for(int i=start; i<N; i++) { //i =start
                // 배열에 넣어줌
                numbers[cnt] = input[i]; 
                // 다재귀를 start+1이 값이 아닌 i+1 
                combination(cnt+1,i+1);
        }
    }

🚨 주요 포인트

조합은 start를 기준으로 (현재 뽑힌 수 다음 i+1)를 호출하기에 중복될 일이 없고 (2,4,6) (4,2,6)과 같은 경우도 제거한다.

중복 조합의 경우, 재귀로 넘길 때 start의 값을 신경 써주면 된다

combination(cnt+1, i) // 자기 자신도 포함될 수 있게

---

💡부분집합(SubSet)

: 집합 A={a, b, c}의 모든 부분집합을 찾아 나열하면 다음과 같다.

∅, {a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c} 즉, A의 부분집합의 총수는 2^n개이다

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        input = new int[N];
        isSelected = new boolean[N];
        for(int i=0; i<N; ++i) {
            input[i] = sc.nextInt();
        }
        generateSubSet(0);

    }

    //count: 현재까지 고려한 원소 수
    private static void generateSubSet(int count) { 

        if(count==N) {
            for(int i=0; i<N; ++i) {
                if (isSelected[i]){
                        System.out.print(input[i]+" ");
                    }
            }
            System.out.println();
            return;
        }

        // 원소 선택
        isSelected[count] = true;
        generateSubSet(count+1);

        // 원소 미선택 
        isSelected[count] = false;
        generateSubSet(count+1);
    }

🚨 주요 포인트

원소를 선택하는 것과 그렇지 않을 때,

2가지로 나누어 구현하는 것이 중요