[개념] 순열, 조합, 부분집합

18429번: 근손실

boj의 근손실 문제를 풀며, 처음으로 Java에서 순열을 구현해보게 되었다.

따라서 순열의 구현을 공부하는 김에, 순열/조합/부분집합까지 공부하였다.

 

순열(Permutation)

순열의 경우, 순서를 신경써주어야 한다. 

(1,2) != (2,1) 이다.

 

아래는 nPr을 구현한 코드이다.

package 완전탐색.permutation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N, R;			//nPr
    static int totalCnt = 0;    //경우의수
    static boolean[] isSelected;
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        isSelected = new boolean[N];

        permutation(0);

        System.out.println(totalCnt);
    }

    private static void permutation(int index){
        if(index == R){
            totalCnt++; //경우의 수 1 증가
            return;
        }
        for(int i = 0; i<N; i++){
            //중복 체크
            if(isSelected[i])   continue;

            isSelected[i] = true;
            permutation(index+1);
            isSelected[i] = false;
        }
    }
}

 

조합(Combination)

조합의 경우, 순서를 신경쓰지 않아도 된다.

(1,2) == (2,1)이다.

다음은 nCr의 경우의수를 구현한 코드이다.

순서를 신경쓰지 않아도 되므로, isSelected배열을 사용하지 않고, 선택한 다음 인덱스부터 for문으로 재귀해주면 된다.

import java.io.*;
import java.util.*;

public class Main{
    //N개 중 R개 뽑음
    static int totalCnt = 0;    //경우의수
    static int N,R;				//숫자 개수, 한 조합의 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        R = Integer.parseInt(br.readLine());

        combination(0,0);

        System.out.println(totalCnt);
    }


    private static void combination(int index,int start) {
        if(index==R) {
            totalCnt++;
            return;
        }
        for (int i=start ; i<N ; i++) {
            combination(index+1, i+1);
        }
    }
}

 

부분집합(PowerSet 또는 SubSet)

N개의 원소가 있는 집합에서, 부분집합의 개수를 구하는 경우이다.

해당 인덱스의 원소를 포함하는가, 포함하지 않는가를 나누어서 재귀해주면 된다.

import java.io.*;
import java.util.*;

public class Main{
    static int totalCnt = 0;    //경우의수
    static int N;				//숫자 개수
    static boolean[] isSelected;
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        isSelected = new boolean[N];
        generateSubSet(0);


        System.out.println(totalCnt);
    }
    private static void generateSubSet(int index) {
        if(index ==N) {
            // 부분집합 완성
            totalCnt++;
            return;
        }

        // 현재 원소를 부분집합에 넣기
        isSelected[index] = true;
        generateSubSet(index+1);
        // 현재 원소를 부분집합에 넣지 않기
        isSelected[index]= false;
        generateSubSet(index+1);
    }


}

 

---

각 코드에 원하는 조건을 추가해서 전체 경우의 수를 탐색할 수 있다.

 

---

출처)

[알고리즘 개념] 순열 조합 부분집합(순조부~)