Permutation

순열

n개의 값 중에서 r개의 숫자를 모든 경우의 순서대로 뽑는 것. 순열의 개수는 n!과 같다.

Swap을 이용한 순열

배열의 값을 직접 바꾸는 방법. 배열의 첫 값부터 순서대로 바꾸며 모든 값을 한 번씩 교환. (depth 를 기준으로 depth보다 작은 값은 고정, 큰 값으로 다시 swap)

*순서가 보장되지 않음

 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 순열

사전식의 순열 구현 가능 (visited - 중복해서 뽑지 않기 위해 체크)

arr: r개를 뽑기 위한 n개의 값

output: 뽑힌 r개의 값

static void perm(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) {
      visitied[i] = true;
      output[depth] = arr[i];
      perm(arr, output, visited, depth+1, n, r);
      visited[i] = false;
    }
  }
}

1. 순열을 담을 배열을 static으로 선언
2. visited배열(boolean)을 N크기로 선언
3. perm(int start, int r, int n) 함수 생성
4. start 0부터 증가시키며 select배열에 저장, visited false 처리