a,b,c가 존재한다고 가정할 경우
순열의 집합은 다음과 같다.
a,b,c
a,c,b
b,a,c
b,c,a
c,a,b
c,b,a
즉 총 6개의 순열이 나오는데 n개의 주어진 원소에 대해 n! 개의 상이한 순열이 있다는 것은 쉽게 알 수 있다.
n! = n * (n-1) * ... * 1
네 개의 원소 {a,b,c,d}로 된 집합을 살펴보면 간단한 알고리즘을 얻을 수 있을 것이다.
이것에 대한 순열의 집합은 다음과 같이 출력시키면 결과를 얻을 수 있다.
1) a로 시작하는 {b,c,d}의 모든 순열
2) b로 시작하는 {a,c,d}의 모든 순열
3) c로 시작하는 {a,b,d}의 모든 순열
4) d로 시작하는 {a,b,c}의 모든 순열
~로 시작하는 ~의 모든 순열 이라는 표현이 바로 순환의 실마리이다.
순열 n개에 대한 알고리즘을 아래와 같이 재 정의 가능하다.
perm( i )
{
만약 마지막 이라면 출력 ( i 가 n-1이라면 출력 ) return;
반복 ( i 부터 n-1 까지 )
{
~로 시작하는
perm( i + 1);
원래 list로 복구
}
}
첫 순환의 ~로 시작하는 순열은 다음과 같다
| 1 , 2 , 3 , 4 | 1과 1를 교환 |
| 2 , 1 , 3 , 4 | 1과 2를 교환 |
| 3 , 2 , 1 , 4 | 1과 3를 교환 |
4 , 2 , 3 , 1 | 1과 4를 교환 |
즉 한번씩 돌아가면서 시작되는 값으로 설정하고 이 값들 각각의 순열를 구하는게 바로 순환의 실마리이다.
1로 시작하는 순열은 다음과 같다
순차적으로 인덱스0 값과 다음 인덱스 값을 교환 하고 ~로 시작하는 순열을 구한다 | 순차적으로 인덱스1 값과 다음 인덱스 값을 교환 하고 | 순차적으로 인덱스2 값과 다음 인덱스 값을 교환 하고~로 시작하는 순열을 구한다 | 더이상 순열이 없으면 출력한다. |
| 1 , 2 , 3 , 4 | |||
1 , 2 , 3 , 4 | |||
| 1 , 2 , 3 , 4 | ||
1 , 2 , 3 , 4 | |||
| 1 , 2 , 4 , 3 | ||
1 , 2 , 4 , 3 |
| |||
1 , 3 , 2 , 4 | |||
| 1 , 3 , 2 , 4 | ||
| 1 , 3 , 2 , 4 | |||
| 1 , 3 , 4 , 2 | ||
| 1 , 3 , 4 , 2 |
| |||
1 , 4 , 3 , 2 | |||
| 1 , 4 , 3 , 2 | 1 , 4 , 3 , 2 | |
| 1 , 4 , 2 , 3 | ||
1 , 4 , 2 , 3 |
나머지 생략.....
코드로 표현하면 다음과 같다.
perm( i , n)
{
if( i 와 n이 같다 )
{
list 0 부터 n 까지 전부 출력
}
else
{
for( j = i ; i <= n ; j++) // i 부터 다시 반복 ( 출력 할 때까지 )
{
list[i] 와 list[j] 를 스왑 // 첫번짼 1 , 2 , 3 , 4 가 되고 두번짼 2 , 1 , 3 ,4 가 세번짼....
perm(list , i + 1 , n );
list[i] 와 list[j] 를 스왑 // 복구
}
}
}
이해하는데 한 참이 걸렸다.
~로 시작하는....하~ *.* b