순열

1. 순열 (Permutation)
순열은 주어진 원소들 중에서 순서를 고려하여 특정 개수의 원소를 선택하는 경우입니다. 주어진 원소들에서 중복 없이 선택한 원소들의 순서가 중요합니다.

예시:
주어진 원소 `{1, 2, 3}`에서 2개를 선택할 때:
- 가능한 순열은 `(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)`입니다.

수학적 정의:
- `n`개의 원소 중에서 `r`개를 선택하는 순열의 수는 `P(n, r) = n! / (n - r)!`입니다.

 

순열 구현:

- 백트래킹은 가능한 모든 경우의 수를 시도하면서 불필요한 부분은 빠르게 가지치기하여 탐색을 줄이는 기법입니다. 순열을 구할 때 주로 사용되며, 각 원소를 선택하는 모든 경우를 탐색합니다.

import java.util.*;

public class Permutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};  // 순열을 구할 배열
        List<List<Integer>> result = new ArrayList<>();
        
        // 순열을 생성하는 함수 호출
        generatePermutations(nums, 0, result);
        
        // 결과 출력
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }

    // 순열을 생성하는 함수 (재귀적 방법)
    public static void generatePermutations(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> current = new ArrayList<>();
            for (int num : nums) {
                current.add(num);
            }
            result.add(current);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            generatePermutations(nums, start + 1, result);
            swap(nums, start, i); // 원상복구 (백트래킹)
        }
    }

    // 배열의 두 원소를 교환하는 함수
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

2. 중복순열 (Permutation with Repetition)
중복순열은 주어진 원소들 중에서 중복을 허용하여 순서대로 선택하는 경우입니다. 원소를 여러 번 선택할 수 있으며, 선택한 원소의 순서가 중요합니다.

예시:
주어진 원소 `{1, 2, 3}`에서 2개를 중복 허용하여 선택할 때:
- 가능한 중복순열은 `(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)`입니다.

수학적 정의:
- 중복순열의 경우, `n`개의 원소에서 `r`개를 선택하는 경우의 수는 `P(n, r) = n^r`입니다.

 

중복순열 구현:

조합을 구하는 방법은 순열과 달리 순서가 중요하지 않으므로, 중복을 피하면서 원소를 선택하는 방식으로 구현됩니다. 재귀적으로 원소를 선택하고, 선택된 원소를 포함한 조합을 탐색합니다. 백트래킹 방식을 사용합니다.

import java.util.*;

public class PermutationWithRepetition {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};  // 순열을 구할 배열
        List<List<Integer>> result = new ArrayList<>();
        
        // 중복순열을 생성하는 함수 호출
        generatePermutations(nums, 0, new ArrayList<>(), result);
        
        // 결과 출력
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }

    // 중복순열을 생성하는 함수 (재귀적 방법)
    public static void generatePermutations(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == 2) {  // 예시에서는 2개의 원소를 선택
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            current.add(nums[i]);
            generatePermutations(nums, i, current, result);  // 인덱스를 i로 그대로 두어 중복을 허용
            current.remove(current.size() - 1);  // 원상복구 (백트래킹)
        }
    }
}

결론
- 순열은 주어진 원소에서 중복 없이 순서대로 원소를 선택합니다. 순서가 중요하며, 각 원소는 한 번만 선택됩니다.
- 중복순열은 원소를 중복해서 선택할 수 있으며, 순서가 중요합니다. 즉, 같은 원소가 여러 번 선택될 수 있습니다.