CaseOfNumber - 조합 & 중복조합 &순열 & 중복순열

CaseOfNumber - 조합 & 중복조합 &순열 & 중복순열

조합(Combination)

서로 다른 물건들 중 몇 가지 대상을 뽑는 것을 조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 X)

중복 조합(Homogeneous)

서로 다른 종류의 대상들 중에서 중복을 허락하여 몇 개를 택하는 조합을 중복조합이라고 한다.

서로 다른 n 개의 원소 중 r 개를 선택 (순서 X, 중복 O)

순열(Permutation)

서로 다른 물건들 중 몇 가지 대상을 뽑아 일렬로 나열하는 것을 순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

중복 순열(Product)

서로 다른 물건들 중에서 중복을 허용하여 몇 개를 택하는 순열을 중복순열이라고 한다.

서로 다른 n개의 원소 중 r개를 선택 (순서O , 중복 O)

code

import java.util.Arrays;

public class MyCombi {
    static int[] data = { 1,2,3,4 };
    static int[] res;
    static boolean[] visit;
    static int cnt;

    public static void main(String[] args) {
        int N = 4, R = 2;
        res = new int[R];
        visit = new boolean[N];

        cnt = 0;
        solve1(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve2(N, R, 0);
        System.out.println(cnt);

        cnt = 0;
        solve3(N, R, 0, 0);
        System.out.println(cnt);

        cnt = 0;
        solve4(N, R, 0, 0);
        System.out.println(cnt);
    }

    //중복순열: 순서가 중요하고(123!=321), 중복을 허용하는 경우
    private static void solve1(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            res[depth] = data[i];
            solve1(n, r, depth + 1);
        }
    }

    //순열: 순서가 중요하고(123!=321), 중복을 허용하지 않는 경우
    private static void solve2(int n, int r, int depth) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = 0; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve2(n, r, depth + 1);
                visit[i] = false;
            }
        }
    }

    //중복조합: 순서가 중요하지 않고(123==321), 중복을 허용하는 경우
    private static void solve3(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            res[depth] = data[i];
            solve3(n, r, depth + 1, i);
        }
    }

    //조합: 순서가 중요하지 않고(123==321), 중복을 허용하지 않는 경우
    private static void solve4(int n, int r, int depth, int start) {
        if (depth == r) {
            System.out.println(Arrays.toString(res));
            cnt++;
            return;
        }

        for (int i = start; i < n; i++) {
            if (visit[i] == false) {
                visit[i] = true;
                res[depth] = data[i];
                solve4(n, r, depth + 1, i);
                visit[i] = false;
            }
        }
    }

}