[조합론] 순열, 조합, 중복 순열, 중복 조합, 부분 집합 정리

알고리즘 시험 대비를 위해서 순열, 조합, 중복 순열, 중복 조합, 부분 집합 내용 정리를 하려고 합니다.

 

순열

서로 다른 n개의 원소에서 r개를 중복 없이 순서에 따라 나열한 것입니다. 예를 들어 1,2,3에서 2개를 골라 나열할 수 있는 경우의 수는 6가지로, (1,2) (1,3), (2,1), (2,3), (3,1), (3,2)가 있습니다.

import java.util.Arrays;

public class PermutationExample {
    private static int[] items = {1, 2, 3};
    private static int[] permutation;
    private static boolean[] used;
    private static int n = items.length;
    private static int r = 2;

    public static void main(String[] args) {
        permutation = new int[r];
        used = new boolean[n];

        permute(0);
    }

    private static void permute(int depth) {
        if(depth == r) {
            System.out.println(Arrays.toString(permutation));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!used[i]) {
                used[i] = true;
                permutation[depth] = items[i];
                permute(depth + 1);
                used[i] = false;
            }
        }
    }
}

- index 상에서 뒤에 있는 원소가 더 앞에 오는 경우도 세야하기 때문에 permute 내부의 반복문은 계속 0부터 시작합니다.

- 중복해서 선택하는 것이 불가능하기 때문에, used 배열을 사용해서, 이미 선택한 원소는 선택하지 않도록 합니다.

 

조합

서로 다른 n개의 원소에서 r개를 중복 없이, 순서 없이 나열한 것입니다. 예를 들어 1,2,3에서 2개를 골라 나열할 수 있는 경우의 수는 3가지로, (1,2), (1,3), (2,3)입니다.

import java.util.Arrays;

public class CombinationExample {
    private static int[] items = {1, 2, 3};
    private static int[] combination;
    private static int n = items.length;
    private static int r = 2;

    public static void main(String[] args) {
        combination = new int[r];

        combine(0, 0);
    }

    private static void combine(int depth, int start) {
        if(depth == r) {
            System.out.println(Arrays.toString(combination));
            return;
        }

        for(int i = start; i < n; i++) {
            combination[depth] = items[i];
            combine(depth + 1, i + 1);
        }
    }
}

- 위의 순열과 다르게, (1,2)를 뽑았다면 (2,1)을 뽑지 않으므로, combine 내부의 반복문은 start에서 시작합니다.

- 조합에서는 한 번 고른 원소는 다시 고르지 않으므로, 대신 i+1을 사용하여, 중복을 허용하지 않습니다.

 

중복 순열

서로 다른 n개의 원소에서 r개를 중복하여, 순서에 따라 나열한 것입니다. 예를 들어, 1,2,3에서 2개를 골라 나열할 수 있는 경우의 수는 9가지로, (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)입니다.

import java.util.Arrays;

public class PermutationWithRepetitionExample {
    private static int[] items = {1, 2, 3};
    private static int[] permutation;
    private static int n = items.length;
    private static int r = 2;

    public static void main(String[] args) {
        permutation = new int[r];

        permute(0);
    }

    private static void permute(int depth) {
        if(depth == r) {
            System.out.println(Arrays.toString(permutation));
            return;
        }

        for(int i = 0; i < n; i++) {
            permutation[depth] = items[i];
            permute(depth + 1);
        }
    }
}

- 중복을 허용하기 때문에, 위의 순열과 달리 used로 사용을 했는지 확인하지 않습니다. 

- 순서에 따라서 나열하기 위해, 0부터 반복문을 돌립니다.

 

중복 조합

서로 다른 n개의 원소에서 중복하여, 순서 없이 나열한 것입니다.  예를 들어, 1,2,3에서 2개를 골라 나열할 수 있는 경우의 수는 6가지로, (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)이 있습니다.

import java.util.Arrays;

public class CombinationWithRepetitionExample {
    private static int[] items = {1, 2, 3};
    private static int[] combination;
    private static int n = items.length;
    private static int r = 2;

    public static void main(String[] args) {
        combination = new int[r];

        combine(0, 0);
    }

    private static void combine(int depth, int start) {
        if(depth == r)
    {
        System.out.println(Arrays.toString(combination));
        return;
    }

    for(int i = start; i < n; i++) {
        combination[depth] = items[i];
        combine(depth + 1, i);
    }
}

- 조합과 달리 중복 조합에서는 각각의 원소마다 가능한 모든 경우의 수를 고려하기 위해, i+1이 아니라 i를 사용하여 중복을 허용합니다. 

 

부분 집합

n개의 원소를 갖는 집합에서 가능한 모든 부분 집합을 구한 것입니다. 예를 들어 1,2,3의 부분 집합은 {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}입니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetExample {
    private static int[] items = {1, 2, 3};
    private static List<List<Integer>> subsets;

    public static void main(String[] args) {
        subsets = new ArrayList<List<Integer>>();
        subset(0, new ArrayList<Integer>());

        for(List<Integer> s : subsets) {
            System.out.println(Arrays.toString(s.toArray()));
        }
    }

    private static void subset(int index, List<Integer> subset) {
        subsets.add(new ArrayList<Integer>(subset));
        for(int i = index; i < items.length; i++) {
            subset.add(items[i]);
            subset(i + 1, subset);
            subset.remove(subset.size() - 1);
        }
    }
}

- 현재 인덱스와 구한 부분 집합을 매개 변수로 받아서 부분집합을 구합니다.