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

순열

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

 

 

DFS 로 for문을 0부터 시작

int (boolean) 배열 visited 사용

[1, 3, 5] 배열에서 순열을 찾는 코드

import java.util.Arrays;

public class Recursive7 {

    static void permutation(int[] arr, int[] p, int[] visited, int idx) {
        if (idx == arr.length) {
            System.out.println(Arrays.toString(p));
            return;
        }

        for (int i=0; i<arr.length; i++) {
            if (visited[i] == 0) {
                visited[i]++;
                p[idx] = arr[i];
                permutation(arr, p, visited, idx+1);
                visited[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5};
        int[] visited = {0, 0, 0};
        int[] p = {0, 0, 0};
        permutation(arr, p, visited, 0);
    }
}

[1, 3, 5]
[1, 5, 3]
[3, 1, 5]
[3, 5, 1]
[5, 1, 3]
[5, 3, 1]

 

 

 

조합

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

 

 

순열의 DFS 코드에서 for문을 시작할 start 변수를 넘겨줌

N개를 뽑기 위해 N 변수도 추가해줌

[1, 3, 5] 배열에서 N개의 조합을 뽑는 코드

import java.util.Scanner;

public class Recursive8 {

    static void combination(int[] arr, int[] p, int[] visited, int idx, int start, int N) {
        if (idx == N) {
            System.out.print("[");
            for (int i=0; i<p.length; i++) {
                if (i==p.length-1) {
                    System.out.print(p[i]);
                    break;
                }
                System.out.print(p[i] + ", ");
            }
            System.out.println("]");
            return;
        }

        for (int i=start; i<arr.length; i++) {
            if (visited[i] == 0) {
                visited[i]++;
                p[idx] = arr[i];
                combination(arr, p, visited, idx+1, i, N);
                visited[i]--;
            }
        }
    }

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

        int[] arr = {1, 3, 5};
        int[] p = new int[N];
        int[] visited = new int[arr.length];

        System.out.println(N + "개뽑기");
        combination(arr, p, visited, 0, 0, N);
    }
}

2개뽑기
[1, 3]
[1, 5]
[3, 5]

 

 

 

부분집합

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

 

 

DFS를 for문을 돌려 1개 뽑기~배열의 사이즈 뽑기 만큼 진행

r개를 다 뽑았다면 출력

[1, 3, 5] 배열의 부분집합 출력 코드

import java.util.Arrays;

public class Recursive9 {
    static void powerSet(int[] arr, int[] p, int[] visited, int idx, int r) {
        if (idx == r) {
            System.out.println(Arrays.toString(p));
            return;
        }

        for (int i=idx; i<arr.length; i++) {
            if (visited[i] == 0) {
                visited[i]++;
                p[idx] = arr[i];
                powerSet(arr, p, visited, idx+1, r);
                visited[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5};
        int[] visited = new int[arr.length];

        for (int i=1; i<=arr.length; i++) {
            int[] p = new int[i];
            powerSet(arr, p, visited, 0, i);
        }
    }
}

[1]
[3]
[5]
[1, 3]
[1, 5]
[3, 5]
[5, 3]
[1, 3, 5]