📚 1. 순열

📖 A. 순열 (Permutation)

✔️ 순열이란?

• 서로 다른 n개의 원소 중 r개를 순서 있게 골라낸 것
• 경우의 수 : n! / (n-r)!

ex)

AB, BA, BC, CB, CA, AC

 

✔️ Algorithm

단순 배열을 이용하여 구현

private static void perm(int cnt){
	if(cnt == N){
		totalCnt++;
		System.out.println(Arrays.toString(numbers));
		return;
	}
	for(int i = 0; i< N ;i++){
		if(!isSelected[i]){
			numbers[cnt] = i;
			isSelected[i] = true; // 선택
			perm(cnt+1);
			isSelected[i] = false; // 선택 해제
		}
	}
}

 

참조형을 사용하여 구현

private static void perm(ArrayList<Integer> list, int count){
	if(cnt == 0){
		totalCnt++;
		System.out.println(list);
		return;
	}
	for(int i = 0; i< N ;i++){
		if(!list.contains(arr[i])){
			list.add(arr[i]);
			perm(list, count - 1); // 뽑을 때마다 count - 1
			list.remove(list.size() - 1); // 재귀를 하기 위해 마지막에 넣은 원소 제거
		}
	}
}

 

 

📖 B. 중복 순열 (Permutation with Repetition)

✔️ 중복 순열이란?

• 서로 다른 n개의 원소 중 r개를 순서를 지키며 골라 낸 것 중 중복을 허용하는 것 (중복 O, 순서 O)
• 경우의 수 : n^r

ex)

AB, BA, BC, CB, CA, AC + AA, BB, CC

 

✔️ Algorithm

단순 배열을 이용하여 구현

// arr 1차원 배열

public static void divPermutation(int r, int[] temp, int current){  
    if(r == current){  
        System.out.println(Arrays.toString(temp));  
        return;  
    }else{  
        for(int i =0; i< arr.length;i++){  
            temp[current] = arr[i];  
            permutation(r, temp, current + 1);  
        }    
    }
}

 

참조형을 사용하여 구현

private static void dupPermutation(ArrayList<Integer> list, int count){
	if(count == 0){
		System.out.println(list);
		dupPerCount++;
		return;
	}

	for(int i =0 ;i< n; i++){
		list.add(arr[i]);
		dupPermutation(list, count - 1); // 뽑을 때마다 count - 1
		list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거
	}
}

 

 

📚 2. 조합

📖 A. 조합 (Combination)

✔️ 조합이란?

• 서로 다른 n개 중에 r개를 선택하는 경우의 수
• 경우의 수 : n!/r!(n-r)!

ex)

AB, AC, BC

 

✔️ Algorithm

배열을 이용하여 구현

// nCr

private static void comb(int cnt, int start){
	if(cnt == R){
		totalCnt++;
		System.out.println(Arrays.toString(numbers));
		return;
	}

	// start부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출
	for(int i = start; i < N; i++){
		// start 위치부터 처리했으므로 중복체크 필요없다.
		// 잎쪽에서 선택되지 않았다면 그 수를 사용한다.
		numbers[cnt] = input[i];
		comb(cnt + 1, i + 1);
	}
}

 

참조 자료형을 사용하여 구현

// nCr, comCount 숫자 센다.

private static void comb(ArrayList<Integer> list, int index, int count){
	if(count == 0){
		System.out.println(list);
		comCount++;
		return;
	}

	for(int i = index; i < n ; i++){
		list.add(arr[i]);
		comb(list, i + 1, count - 1);
		list.remove(list.size() - 1); // 재귀를 위해 마지막에 넣은 원소 제거
	}
}

 

 

📖 B. 중복 조합 (Combination with Repetition)

✔️ 중복 조합이란?

• n개중에 r개를 선택하는 경우의 수
• 경우의 수 : (r + (n-1))! / r!(n-1)!

ex)

AB, AC, BC + AA, BB, CC

 

✔️ Algorithm

배열을 이용하여 구현

// N : 총 갯수, R : 선택한 갯수
// numbers = new int[R];
// arr = new int[N+1];

private static void dupComb(int cnt, int start) {  
    if (cnt == R) {  
        totalCnt++;  
        System.out.println(Arrays.toString(numbers));  
        return;  
    }  
    for (int i = start; i <= N; i++) {  
        numbers[cnt] = arr[i];  
        dupComb(cnt + 1, i);  
    }
}

결과

n 입력 : 5
R 입력 : 3
첫 번째 실행
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
[1, 1, 6]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 3]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 4]
[1, 4, 5]
[1, 4, 6]
[1, 5, 5]
[1, 5, 6]
[1, 6, 6]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 2, 5]
[2, 2, 6]
[2, 3, 3]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 4]
[2, 4, 5]
[2, 4, 6]
[2, 5, 5]
[2, 5, 6]
[2, 6, 6]
[3, 3, 3]
[3, 3, 4]
[3, 3, 5]
[3, 3, 6]
[3, 4, 4]
[3, 4, 5]
[3, 4, 6]
[3, 5, 5]
[3, 5, 6]
[3, 6, 6]
[4, 4, 4]
[4, 4, 5]
[4, 4, 6]
[4, 5, 5]
[4, 5, 6]
[4, 6, 6]
[5, 5, 5]
[5, 5, 6]
[5, 6, 6]
[6, 6, 6]

Process finished with exit code 0

 

참조 자료형을 사용하여 구현

public static void dupCombination(ArrayList<Integer> list, int index, int count){
	if (count == 0){
		System.out.println(list);
		dupComCount++;
		return;
	}

	for(int i = index; i <= N; i++){
		list.add(arr[i]);
		dupCombination(list, i, count - 1); // 뽑을 때마다 count - 1
		list.remove(list.size() - 1); // 재귀 위해 마지막에 넣은 원소 제거
	}
}

 

 

📚 3. 부분 집합

✔️ 부분 집합이란?

• 공집합을 포함한 모든 원소의 경우의 수
• 부분집합의 총 개수 : 2^N

ex)

{1, 2, 3}
- {}, {1}, {2}, {3}, {1, 2}, {1, 3}, ~ , {1, 2, 3}

 

✔️ Algorithm

import java.util.Scanner;

public class test {

    static int N, totalCnt;
    static int[] input;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        totalCnt = 0;
        input = new int[N];
        isSelected = new boolean[N];

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

        subset(0);
        System.out.println("총 경우의 수 : " + totalCnt);

    }

    private static void subset(int index){ // cnt : 직전까지 고려한 원소 수

        if(index == N){ // 더이상 고려할 원소가 없다면 부분집합의 구성이 완성
            for(int i = 0; i < N; i++){
                System.out.print(isSelected[i] ? input[i]:"X");
                System.out.print("\t");
            }
            System.out.println();

            return;
        }

        // 원소 선택
        isSelected[index] = true;
        subset(index +1);

        // 원소 미선택
        isSelected[index] = false;
        subset(index + 1);


    }
}

 

✔️ 전체적인 소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution1016{

    static int N, R;
    static int[] number;
    static boolean[] visited;


    // 순열
    // 1 2 3
    // 12, 13
    // 21, 23
    // 31, 32
    static void prim(int idx){
        if(idx == R){
            System.out.println(Arrays.toString(number));
            return;
        }

        for(int i =1 ;i<=N; i++){
            if(!visited[i]){
                number[idx] = i;
                visited[i] = true;
                prim(idx + 1);
                visited[i] = false;
            }

        }
    }

    // 조합
    // 1 2 3
    // 12, 13
    // 23
    static void comb(int idx, int cnt){
        if(idx == R){
            System.out.println(Arrays.toString(number));
            return;
        }

        for(int i=cnt; i<= N; i++){
            number[idx] = i;
            comb(idx + 1, i + 1);
        }

    }


    static int idxCnt;
    static ArrayList<Integer> resArr;
    // 부분집합
    // 1 2 3 4
    // 1 2 3, 1 2 4, 1 2, 1 3 4, 1 3, 1 4, 1
    // 2 3 4, 2 3, 2 4, 2, 3 4, 3, 4
    static void divde(int idx){
        if(idx == N){
            for(int i =0; i< N; i++){
                if(visited[i]){
                    resArr.add(i);
                }
            }
            System.out.println(resArr);
            resArr = new ArrayList<>();
            return;
        }

        visited[idx] = true;
        divde(idx + 1);

        visited[idx] = false;
        divde(idx + 1);

    }

    public static void main(String[] args) throws IOException {
        // 순열, 조합, 부분집합 구현해보기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        number= new int[R];
        visited = new boolean[N+1];

        // 순열
//        prim(0);
        number= new int[R];
        visited = new boolean[N+1];

//        comb(0, 0);

        number= new int[N+1];
        visited = new boolean[N+1];
        resArr = new ArrayList<>();
        divde(1);


        br.close();
    }
}

 

 

---

참조

• https://hanyeop.tistory.com/362