[기초 수학] 순열

| 순열 (permutation)

✏️ 개념 정리

(1) 팩토리얼 : 서로다른 N개의 수를 일열로 나열하는 전체 경우의 수

- 1~n까지 모든 자연수의 곱 (n!) --- 단, 0!은 1이다.

- n! = n*(n-1)...*1

(2) 순열 : 서로 다른 N개의 수에서 R개를 뽑아 나열하되, 순서대로 나열하는 경우의 수

- 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서 O, 중복 X)

- nPr = n! / (n-r)! = n(n-1)(n-2)....(n-r+1) (단, 0<r<=n)

(3) 중복 순열 : 서로 다른 n개 중 r개를 선택하는 경우의 수 (순서 O, 중복 O)

- nㅠr = n의 r 승

(4) 원 순열 : 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수

- n!/n = (n-1)!

💻 구현하기

[ 순열 구현 1_ 재귀 : 깊이에 따른 순차 교환 ]

✅ 순열 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하여 나열하는 것

✅ 구현 방법

[입력]

서로 다른 n개의 수를 담은 배열과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r)를 인자로 받는다.

*알고리즘이 시작되면, 깊이 인덱스(depth)는 0이다.

*깊이는 선택하려는 숫자의 인덱스를 의미한다.

[처리]

현재 깊이(depth=0)와 깊이 인덱스부터(i=depth)~배열의 끝(i=n-1)까지 중 하나를 교환하고 깊이를 높혀줄 것이다.

1. 현재 깊이 인덱스(depth=0)와 하나의 인덱스(i=depth=0)를 교환한다.

2. 깊이 인덱스를 하나 높혀준다.(depth=0+1=1)

2. 위의 1)~2) 과정을 반복한 뒤, 선택 가능 갯수를 초과할 때(depth == r) 탈출한다.

3. 탈출 후 더 낮은 깊이에서 정상교환이 이루어지도록 교환한 것을 재교환한다.

※ 그림으로 본 순열 알고리즘 모습

✅ 구현 하기

void permutation(int[] arr, int depth, int n, int r) {

    if (depth == r) {
        for (int i = 0; i < r; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        return;
    }

    for (int i = depth; i < n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }

}

public void swap(int[] arr, int a, int b) {
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

[ 순열 구현 2_ 재귀 : 교환 없이 추가배열을 통해 출력하기 ]

✅ 순열 : 서로다른 n개의 수에서 r개를 중복없이 순서를 고려하여 나열하는 것

✅ 구현 방법

[입력]

서로 다른 n개의 수를 담은 배열(int[] arr)과, 깊이 인덱스(depth), 배열의 길이(n), 선택하려는 갯수(r),

방문위치를 알려줄 배열(int[] visited), 출력 배열(int[] out)을 인자로 받는다.