[알고리즘] 2-2. 순열

순열 (Permutation)

-> 가능한 열의 순서 (n개면 n!)

 

첫 번째 원소를 임의로 지정하고, 나머지의 순열을 출력

-> 지정하는 원소의 개수를 하나씩 늘려가면서 순열 출력

 

즉, 집합 S의 각 원소 x에 대해서 S-{x}의 모든 순열을 생성 후, 각각의 맨 앞에 x를 추가해 출력한다.

 

 

순환함수가 데이터 변경시, 호출 전후에 데이터가 변경되지 않고 유지되도록 정의 [데이터의 동일성 유지]

 

-> data [0...k-1]을 prefix로, data[k..n]으로 만들 수 있는 모든 순열을 출력

-> 단, 배열 data에 저장된 값들의 순서는 그대로 유지

 

char data[] = {'a','b','c','d'};
int n=4;

void perm(int k) {
 if (k==n) {
  print data[0...n-1];
  return;
 }
 
 for (int i=k; i<n; i++) {
  swap(data, k, i);
  //swap data[k] and data[i] : data 배열의 k번째와 i번째의 순서를 바꾼다.
  
  perm(data, k+1, n);
  swap(data, k, i);
 }
 
}