순열(Permutation)

1. 순열의 개념 (Permutation)

순열은 서로 다른 n개의 원소 중에서 r개를 순서를 고려하여 나열하는 경우

• 순서가 중요하다.
• 예: [1, 2, 3] 중 2개를 뽑는 경우
  → 가능한 순열: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2]

 2. 순열 공식

nPr = n! / (n - r)!

• !는 팩토리얼(factorial). 예: 4! = 4 × 3 × 2 × 1 = 24
• 예: 3개 중 2개를 순서 있게 뽑는 경우
  → 3P2 = 3! / (3-2)! = 6

3. Java 코드로 예시

예제 1:  nPr 계산 (순열 공식으로 계산)

public class PermutationFormula {

    public static void main(String[] args) {
        int n = 5;
        int r = 3;
        int result = permutation(n, r);
        System.out.println(n + "P" + r + " = " + result);
    }

    static int permutation(int n, int r) {
        return factorial(n) / factorial(n - r);
    }

    static int factorial(int n) {
        int result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

실행 결과:

5P3 = 60

예제 2: 실제 순열을 출력하 (재귀/백트래킹)

public class PermutationPrint {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        boolean[] visited = new boolean[arr.length];
        int[] output = new int[2]; // 2개만 뽑는 경우

        permutation(arr, output, visited, 0, 2); // 3P2
    }

    static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int r) {
        if (depth == r) {
            print(output, r);
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth + 1, r);
                visited[i] = false; // 백트래킹
            }
        }
    }

    static void print(int[] arr, int r) {
        for (int i = 0; i < r; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

 

실행결과

1 2 
1 3 
2 1 
2 3 
3 1 
3 2