순열 (Permutation)이란?

n개의 값 중에서 r개의 숫자를 모든 순서대로 뽑는 경우를 말한다.
예를 들어, [1, 2, 3] 이라는 3개의 배열에서 2개의 숫자를 뽑는 경우는

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

이렇게 6개이다.

1. Swap을 이용한 순열

첫 번째는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법이다.
배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한 번씩 swap 한다.
depth를 기준 인덱스로 하여 depth보다 인덱스가 작은 값들은 그대로 고정하고
depth보다 인덱스가 큰 값들만 가지고 다시 swap을 진행한다.

https://github.com/ParkJiwoon/Algorithm/blob/master/Algorithm/image/perm_1.png

간단하고 코드가 깔끔하지만, 순열들의 순서가 보장되지 않는다.

Java Code

// 순서없이 n개 중에서 r개를 뽑는 경우
// 사용 예시 : permutation(arr, 0, n, 4);
static void permutation(int[] arr, int depth, int n, int r) {
	if(depth == r) {
		print(arr, r);
		return;
	}
	
	for(int i = depth; i < n; i++) {
		swap(arr, depth, i);
		permutation(arr, depth + 1, n, r);
		swap(arr, depth, i);
	}
}

static void swap(int[] arr, int depth, int i) {
	int temp = arr[depth];
	arr[depth] = arr[i];
	arr[i] = temp;
}

---

Visited 배열을 이용한 순열 (DFS)

두 번째로는 visited 배열을 이용하는 방법입니다.
1번과 달리 사전식으로 순열을 구현할 수 있다.

변수	설명
arr	r개를 뽑기 위한 n개의 값
output	뽑힌 r개의 값
visited	중복해서 뽑지 않기 위해 체크하는 값

DFS를 돌면서 모든 인덱스를 방문하여 output에 값을 넣는다.
이미 들어간 값은 visited 값을 true로 바뀌어 중복하여 넣지 않도록 한다.
depth 값은 output 에 들어간 숫자의 길이라고 생각한다.
depth의 값이 r만큼 되면 output에 들어있는 값을 출력한다.

https://github.com/ParkJiwoon/Algorithm/blob/master/Algorithm/image/perm_2.png

---

전체 코드

package Permutation_Combination;

/*
 *  순열 Permutation : n 개 중에서 r개를 순서 있게 뽑기
 *  시간복잡도 : O(n!)
 */

public class Permutation {
	public static void main(String[] args) {
		int n = 3;
		int[] arr = {1, 2, 3};
		int[] output = new int[n];
		boolean[] visited = new boolean[n];
		
		permutation2(arr, output, visited, 0, n, 3);
		System.out.println();
		permutation(arr, 0, n, 3);
		
	}
	
	// 1. Swap으로 구현한 순열  
	// 순서없이 n개 중에서 r개를 뽑는 경우
	// 사용 예시 : permutation(arr, 0, n, 4);
	static void permutation(int[] arr, int depth, int n, int r) {
		if(depth == r) {
			print(arr, r);
			return;
		}
		
		for(int i = depth; i < n; i++) {
			swap(arr, depth, i);
			permutation(arr, depth + 1, n, r);
			swap(arr, depth, i);
		}
	}
	
	static void swap(int[] arr, int depth, int i) {
		int temp = arr[depth];
		arr[depth] = arr[i];
		arr[i] = temp;
	}
	
	// 2. Visited 배열을 이용한 순열 (DFS)
	// 사전 순으로 순열 구하기
	// 사용 예시 : permutation2(arr, output, visited, 0, n, 3);
	static void permutation2(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
		if(depth == r) {
			print(output, r);
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(visited[i] != true) {
				visited[i] = true;
				output[depth] = arr[i];
				permutation2(arr, output, visited, depth + 1, n, r);
				output[depth] = 0;	// 이 줄을 없어도 됨
				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();
	}
}

---

참고자료

https://bcp0109.tistory.com/14