[자료구조] 순열 (Permutation)

1. 팩토리얼

• 1에서 n까지 모든 자연수의 곱 (n!)
• n! = n(n - 1)(n - 2) ... 1

2. 순열

• 순서를 정해서 나열
• 서로 다른 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)!

5. 코드

// 1. 팩토리얼
// 기본 풀이
int n = 5;
int result = 1;

for (int i = 1; i <= n; i++) {
	result *= i; // 120
}

// stream 사용
IntStream.range(2, 6).reduce(1, (x, y) -> (x * y)); // 120

// 2. 순열
/ 5명을 3줄로 세우는 경우의 수
n = 5;
int r = 3;
result = 1;

for (int i = n; i >= n-r+1; i--) {
	result *= i; // 60
}

// 3. 중복 순열
// 서로 다른 4개의 수 중 2개를 뽑는 경우의 수 (중복 허용)
n = 4;
r = 2;
result = 1;

// 기본 풀이
for (int i = 0; i < r; i++) {
	result *= n; // 16
}

// Math 함수 사용
Math.pow(n, r); // 16

// 4. 원 순열
// 원 모양의 테이블에 3명을 앉히는 경우의 수
n = 3;
result = 1;

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

// 순열 구현 - swap
private static 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);
    }
}

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

// 순열 구현 - 방문 처리
private static void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
	if(depth == r) {
        System.out.println(Arrays.toString(out));
        return;
    }
    
    for(int i = 0; i < n; i++) {
    	if(visited[i] != true) {
        	visited[i] = true;
            out[depth] = arr[i];
            permutation(arr, depth + 1, n, r, visited, out);
            visited[i] = false;
        }
    }
}