순열 (Permutation)

* 순열 (Permutation)

 : 서로 다른 n개의 원소에서 r개를 중복을 허용하지 않고 선택하여 순서 있게 늘어 놓은 것을 nPr로 표시한다

문제. 

{ 1, 2, 3, 4  } arr 배열의 4개의 원소에서 3개를 중복을 허용하지 않고 선택하여 순서 있게 나열하는 모든 경우의 수를 출력하시오. (Java)

풀이.

Permutation을 구현하려면 어떻게 해야 할까? 

아래 그림을 보고 힌트를 얻어보자.

출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/

재귀(Recursive) - dfs를 이용하여 풀 수 있을 것 같다.

int[] arr = { 1, 2, 3, 4 };

1) arr[0] → arr[1] → arr[2] → arr[3] 순서로 진행하자.

2) 첫 번째로, arr[0]의 값은 [0], [1], [2], [3]과 swap될 수 있다.

3) 두 번째로, arr[1]의 값은 [1], [2], [3]과 swap될 수 있다.

4) 세 번째로, arr[2]의 값은 [2], [3]과 swap될 수 있다.

5) 네 번째로, arr[3]의 값은 [3]과 swap될 수 있다.

6) for loop을 이용하자

7) 첫 번째로, arr[depth]의 값은 [int i = depth], [i+1], [i+2], [i+3]과 swap될 수 있다.

8) 두 번째로, arr[depth + 1]의 값은 [i = depth], [i+1], [i+2]과 swap될 수 있다.

9) 세 번째로, arr[depth + 2]의 값은 [i = depth], [i+1]과 swap될 수 있다.

10) 네 번째로, arr[depth + 3]의 값은 [i = depth]과 swap될 수 있다.

11) for i < n, arr[depth]의 값은 [int i = depth], [i++], [i++], [i++]과 swap. 

12) for i < n, arr[depth++]의 값은 [i = depth], [i++], [i++]과 swap.

13) for i < n, arr[depth++]의 값은 [i = depth], [i++]과 swap.

14) for i < n, arr[depth++]의 값은 [i = depth]과 swap. if(depth == k)  return

static void permutation(int[] arr, int depth, int n, int k) { if (depth == k) { printPermutation(arr, k); return; } for (int i = depth; i < n; i++) { swap(arr, i, depth); permutation(arr, depth + 1, n, k); swap(arr, i, depth); } } static void printPermutation(int[] arr, int k) { for (int i = 0; i < k; i++) { System.out.print(arr[i] + " "); } System.out.println(); } static void swap(int[] arr, int i, int j) { int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

          // depth가 0일 때, i는 0, 1, 2, 3

          // 즉, arr[0]이 [0], [1], [2], [3]으로 각각 swap된다.

for (int i = depth; i < n; i++) {

swap(arr, i, depth);

 // 다음 depth로 진입한다.

permutation(arr, depth + 1, n, k);

                        // 현재 depth-현재 loop의 다음 iteration을 위해 바꾼 것을 원복.

swap(arr, i, depth);

}