순열 Permutation 알고리즘

{a, b, c, d} 로 순열을 만드는 것은 4! = 24개

 

{a, b, c, d}의 모든 순열  =    첫 원소가 a이면서 {b, c, d}의 모든 순열 

+ 첫 원소가 b이면서 {a, c, d}의 모든 순열 

+ 첫 원소가 c이면서 {a, b, d}의 모든 순열 

+ 첫 원소가 d이면서 {a, b, c}의 모든 순열 

 

위의 식을 보면 함수를 recursive 하게 짤수 있다는 것을 알수 있습니다.

 

첫 원소가 a이면서 {b, c, d}의 모든 순열  =   앞에 고정된 원소 a, b 이면서 {c, d}의 모든 순열

                                               + 앞에 고정된 원소 a, c 이면서 {b, d}의 모든 순열

                                               + 앞에 고정된 원소 a, d 이면서 {b, c}의 모든 순열

 

여기서 앞에 고정된 원소 들을 prefix string

전체 원소를 set S라고 할 때 유사 코드로 작성하면 다음과 같습니다.

void printPerm(prefixString, setS){
  if setS is 0
      print prefixString;
  else
      for each element x in setS
          printPerm(prefixString + x, setS - {x});
}

 

고정 원소를 제외한 집합의 원소 갯수가 0개 이면 고정원소들은 순서대로 출력 

아직 고정되지 않은 원소가 남아 있으면 고정된 원소로 넣고 다시 함수를 반복 합니다.

이제 다시 java code로 함수를 작성하면 다음과 같습니다.

public static void perm(int[] arr, int pivot) {
	if(pivot == arr.length) {
		print_arr();
		return;
	}

	for(int i=pivot;i<arr.length;i++) {
		swap(i, pivot);
		perm(arr, pivot+1);
		swap(i, pivot);
	}
}

 

여기서 pivot은 prefixString의 마지막 index 번호를 의미 합니다. 

pivot 과 arr의 길이가 같다면 arr 전체가 prefixString이므로 집합 전체 출력

 

아니면 모든 경우의수를 나타내기 위해

pivot위치 부터 마지막 index 까지 swap을 하는 recursive를 합니다.

한번 swap 한 이후에 똑같은 배열의 순서에서 경우의수를 진행하기 위해 

for문에서 recursive 이후에 swap을 한번 더 넣어 원래의 배열의 순서로 되돌려 놓고

그 다음 순서를 진행 하게 합니다.