완전 탐색 - 순열, 중복 순열, 조합, 중복 조합, 부분 집합

1. 순열(Permutation)

 

순열

- 서로 다른 n개 중 r개를 순서를 고려하여 선택하는 것

- n = 6, r = 4 이면, P(6, 4) = 6 X 5 X 4 X 3 = 360

- 경우의 수가 11! 이 넘으면 순열로 풀 수 없음(경우의 수: 4억 이상)

n개중 순서를 고려하여 r개를 선택하는 경우의 수

 

코드로 보는 순열

- 원소와 N, R이 주어졌을 때 순열을 구하는 코드

import java.util.Arrays;
import java.util.Scanner;

public class Test {
    static int N, R;
    static boolean[] isSelected;
    static int[] input, output;

    private static void permutation(int cnt){
        if(cnt == R){                                           // R개를 뽑았을 때
            System.out.println(Arrays.toString(output));
            return;
        }

        for(int i=0; i<N; i++){
            if(isSelected[i]){                                  // 이미 뽑은 원소라면 제외
                continue;
            }
            isSelected[i] = true;
            output[cnt] = input[i];                             // 뽑은 후 결과 배열에 넣기
            permutation(cnt+1);
            isSelected[i] = false;
        }
    }

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

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

output
[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]
*/

 

 

중복 순열

- 서로 다른 n개 중 r개를 순서를 고려하여 선택하는데 이미 선택한 것을 중복해서 선택하는 것을 허용

- 순열을 구하는 코드에서 값이 중복인지 체크하는 코드를 빼면 됨

중복 순열

 

코드로 보는 중복 순열

import java.util.Arrays;
import java.util.Scanner;

public class Test {
    static int N, R;
//    static boolean[] isSelected;                              // 중복 허락이므로 주석처리
    static int[] input, output;

    private static void permutation(int cnt){
        if(cnt == R){                                           // R개를 뽑았을 때
            System.out.println(Arrays.toString(output));
            return;
        }

        for(int i=0; i<N; i++){
//            if(isSelected[i]){                                  // 중복 체크 부분 주석처리
//                continue;
//            }
//            isSelected[i] = true;
            output[cnt] = input[i];                             // 뽑은 후 결과 배열에 넣기
            permutation(cnt+1);
//            isSelected[i] = false;
        }
    }

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

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

output
[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 2]
[3, 3]

*/

 

2. 조합(Combination)

 

조합

- 서로 다른 n개 중 r개를 순서 없이 선택하는 것

- n = 6, r = 4 이면, C(6, 4) = 6!/(4!X2!) = 15

- 조합의 재귀적 표현 : nCr = (n-1)C(r-1) + (n-1)C(r) 

n개중 순서를 고려하지 않고 r개를 선택하는 경우의 수

 

코드로 보는 조합

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Test {
    static int[] tmp;
    static int[] arr;
    static int n;
    static int r;

    private static void combination(int cnt, int idx){
        if(cnt == r){
            System.out.println(Arrays.toString(tmp));
            return;
        }

        for(int i=idx; i<n; i++){
            tmp[cnt] = arr[i];
            combination(cnt+1, i+1);
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        arr = new int[n];
        tmp = new int[2];

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

 

 

중복 조합

- 서로 다른 n개 중 r개를 순서를 고려없이 선택하는데 이미 선택한 것을 중복해서 선택하는 것을 허용

중복 조합

코드로 보는 중복 조합

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Test {
    static int[] tmp;
    static int[] arr;
    static int n;
    static int r;

    private static void combination(int cnt, int idx){
        if(cnt == r){
            System.out.println(Arrays.toString(tmp));
            return;
        }

        for(int i=idx; i<n; i++){
            tmp[cnt] = arr[i];
            combination(cnt+1, i);		// 조합은 i+1부터, 중복조합은 i부터
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        r = sc.nextInt();
        arr = new int[n];
        tmp = new int[2];

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

 

3. 부분 집합(Subset)

 

부분 집합

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

- 원소가 n개일때 부분집합의 개수는 2^n

부분 집합

 

코드로 보는 부분 집합

import java.io.IOException;
import java.util.Scanner;

public class Test {
    static boolean[] isSelected;
    static int[] arr;
    static int n;

    private static void SubSet(int cnt, int idx){
        if(idx == n){
            for(int i=0; i<n; i++){
                if(isSelected[i]){
                    System.out.print(arr[i]+" ");
                }
            }
            System.out.println();
            return;
        }

        SubSet(cnt, idx+1);               // 선택 안함
        isSelected[idx] = true;
        SubSet(cnt+1, idx+1);         // 선택 함
        isSelected[idx] = false;
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        isSelected = new boolean[n];

        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        SubSet(0,0);
    }
}
/*
[input]
3
1 2 3

[output]

3 
2 
2 3 
1 
1 3 
1 2 
1 2 3 
*/