순열이란?
집합을 순서있게 나열한 것, 중복이 있을수도 있고 없을수도 있음.
순열의 모든 경우의 수는 n! 개임
순열을 구하려면 특정 원소를 제외한 모든 순열을 나타낸 다음 해당 원소를 붙여서 출력하면 된다.
그림으로 나타내면 아래와 같다.
이를 수도코드로 나타내면 다음과 같다. S의 모든 순열들을 생성한 후 각각에 prefix를 붙이면 된다.
base case는 집합 S가 공집합일 때 문자열 prefix를 출력해주면 된다.
일반 case는 재귀적으로 집합 S의 각각 원소에 대하여 prefix로 삼고, prefix로 삼은 문자열을 제외한 집합 S를 인자로 갖는 재귀함수를 호출한다.
코드로 나타내면 다음과 같이 인덱스를 이용해 더 간명하게 나타낼 수 있다. 또 data 배열을 전역으로선언했기 때문에 data 배열을 인자로 넘길 필요도 없다.
base case는 k==n 일때고 이는 집합 S가 공집합이며 k가 맨 끝으로 이동했을 때를 의미한다.
그때 prefix 문자열은 0부터 n-1 까지 배열전체가 된다.
일반 case는 각각의 원소에 대해 대장을 시켜주면 된다. 즉 해당 원소를 제외한 나머지 원소들에 대해 순열을 구하고 해당 원소를 붙여주는 것이다. 코드로는 k번째 원소와 i번째 원소를 교환하고 나머지 원소들에 대한 순열을 구하기 위한 재귀함수를 호출한다.
하지만 실제 실행시켜보면 중복된 값을 출력한다.
그림과 같이 원소에 번호가 주어졌다고 치자. e 를 대장으로 두고 나머지 원소들에 대해 순열을 진행하려고 한다. 이후 f, g, h 순서로 대장을 할 것이다. 그런데 만약 코드가 재귀적 수행을 하면서 원소들의 원래 자리를 바꿔버린다면? 모든 원소들이 대장을 할 수 없게 되고 이상한 값이 출력된다.
위 그림과 같이 재귀적으로 순열을 수행했을 때 h, g를 swap 한다면 {e, f, h, g} 와 같은 순서가 되면서 수행을 마치는 경우도 있다. 이때 수행을 마치고 돌아오면 순열의 순서가 원래의 순서 {e, f, g, h} 와 달라지므로 문제가 생긴다. 이러한 순서를 보정해주는 작업이 필요하다.
순서가 유지되도록 하는게 중요하다.
코드는 아래와 같고 실제로 실행해보면 제대로 실행되는 것을 확인할 수 있다.
귀납법으로 위 코드가 Mission에 맞게 제대로 동작하는지 확인을 해보면,
base case에서 집합은 공집합이 된다. 즉 0부터 n-1 까지를 prefix로 가지며 이를 공집합과 같이 출력하면 전체가 출력되고 data 배열에 저장된 값들의 순서는 유지되므로 성립한다.
일반 케이스에서 재귀호출을 했을 때 Mission을 제대로 수행한다고 가정하자.
즉 perm(k+1)은 k번째까지를 prefix로 가지며 k+1번째부터 순열을 만들어 출력한다. 모든 작업을 수행 후 해당 함수를 빠져나올땐 원래 순서가 유지된채로 나온다는 뜻이다.
그러면 for 루프만 미션을 제대로 달성하는지 확인하면 된다.
- 맨 처음 swap을 통해서 순서가 뒤바뀐다.
- perm 재귀 호출을 해서 나오고 앞서 뒤바뀐 순서는 유지된다.
- 이를 다시 swap 해주면 맨 처음 swap 해주기 전의 상태로 되돌아 간다.
- 루프를 돌면서 i번째 값과 k번째 값을 바꿔주면서 순열을 수행한다.
위 설명이 잘 이해가 안되겠지만 꼭 이해를 해서 넘어가길 바란다.
상태 공간 트리 (어떤 문제의 모든 해를 포함하고 있는 트리, 해공간트리 라고도 함 )
그래서 순열 문제를 풀땐 상태공간트리를 염두해두고 트리의 모든 노드들을 일정한 규칙에 의해 순회하여 마지막 리프노드들을 출력하는 것이라고 생각하면 된다.
출처
권오흠 교수님의 알고리즘 강의
