[알고리즘 TIL] 조합, 순열, 중복조합, 중복순열 구현하기

중복 조합

1. 배열을 1로 초기화한다.

2. 배열의 맨 뒤 인덱스부터 돌면서 숫자를 증가시킬 수 있는 인덱스를 탐색한다. (기준은 배열의 숫자가 n보다 작은지!!)

3. 해당 인덱스의 숫자를 1 증가시킨다.

4. 해당 인덱스부터 맨 뒤 인덱스까지, 증가된 숫자와 동일한 숫자로 변경한다.

5. 인덱스가 0보다 작아질 때까지 반복한다.

public static void 중복조합(int n, int r) {
        int[] nums = new int[r];
        Arrays.fill(nums, 1);

        while(true) {
            System.out.println(Arrays.toString(nums));

            int index = r - 1;
            while (index >= 0 && nums[index] == n) {
                index--;
            }
            if (index < 0) break;
            nums[index]++;
            for (int i = index + 1; i < r; i++) {
                nums[i] = nums[index];
            }
        }
    }

중복 순열

1. 배열을 1로 초기화한다.

2-1. 배열의 맨 뒤 인덱스부터 돌면서 숫자를 증가시킬 수 있는 인덱스(n이 아닌 경우)를 탐색한다.

2-2. 탐색하는 과정에서 증가시킬 수 없는 인덱스의 숫자는 1로 변경하고, cnt를 +1 한다. 그 후, 다음 인덱스로 넘어간다.

3. 증가시킬 수 있는 인덱스를 찾은 경우 +1을 한 후, 다시 반복한다.

4. cnt가 r과 같아진 경우 종료한다.

public static void 중복순열(int n, int r) {
        int[] nums = new int[r];
        Arrays.fill(nums, 1);

        while (true) {
            int cnt = 0;
            System.out.println(Arrays.toString(nums));
            for (int i = r - 1; i >= 0; i--) {
                if (nums[i] == n) {
                    nums[i] = 1;
                    cnt++;
                    continue;
                }
                nums[i] += 1;
                break;
            }
            if (cnt == r) break;
        }
    }

조합

1. 배열을 초기화한다. (1,2,3)

2. 배열의 맨 뒤 인덱스부터 돌면서 숫자를 증가시킬 수 있는 인덱스를 탐색한다. (기준은 배열의 숫자가 n - r + index + 1보다 작은지!!)

=> n - r + index + 1은 각 인덱스의 숫자가 가질 수 있는 숫자 최댓값

3. 해당 인덱스의 숫자를 1 증가시킨다.

4. 해당 인덱스부터 맨 뒤 인덱스까지, 증가된 숫자보다 순서대로 +1, +2 .. 크게 숫자를 변경한다.

5. 인덱스가 0보다 작아질 때까지 반복한다.

public static void 조합(int n, int r) {
        int[] nums = new int[r];
        for (int i = 0; i < r; i++) {
            nums[i] = i + 1;
        }

        while(true) {
            System.out.println(Arrays.toString(nums));

            int index = r - 1;
            while (index >= 0 && nums[index] == (n - r + index + 1)) {
                index--;
            }
            if (index < 0) break;
            nums[index]++;

            for (int i = index + 1; i < r; i++) {
                nums[i] = nums[i-1] + 1;
            }
        }
    }

순열

1. 조합 알고리즘을 활용하여, 가능한 조합을 모두 찾는다.

2. 각 조합마다 순서를 변경하여 가능한 순열을 모두 찾는다.

2-1. arr[i] < arr[i + 1]인 가장 큰 i를 찾는다. (i가 없으면 (즉, 내림차순이면) 마지막 순열이므로 종료.)

 

2-2. arr[j] > arr[i]인 가장 큰 j를 찾는다. 

 

2-3. arr[i]와 arr[j]를 swap 한다.

2-4. arr[i+1]부터 끝까지를 오름차순으로 정렬한다. (== reverse)

 

 

2-5. 반복한다.

public static void 순열(int n, int r) {
        int[] nums = new int[r];
        for (int i = 0; i < r; i++) {
            nums[i] = i + 1;
        }

        do {
            System.out.println(Arrays.toString(nums));
        } while (permutation(nums));
    }

    private static boolean permutation(int[] arr) {
        int i = arr.length - 2;

        // 1. 뒤에서부터 오름차순 깨지는 지점 찾기
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i < 0) return false;

        // 2. 교환할 자리 찾기
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;

        // 3. 교환
        swap(arr, i, j);

        // 4. 뒤집기
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }

    private static void reverse(int[] arr, int i, int j) {
        while (i < j) swap(arr, i++, j--);
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }