예제 1.4 순환순열생성기

자 2년7개월간 굳은 머리로 3일내내 들여다본 내용을 설명해본다.

("   printf("(1)i:%d,j:%d\n",i,j);   "  <--요런거 i, j 값 확인차 심어논 printf문이다)

자료구조책 12p 예제 1.4 순환순열성기.

program #1. 순환순열생성기

#include <stdio.h>
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void perm(char *list, int i, int n);
void main() {
 char list[3] = {'a','b','c'};
 perm(list, 0, 2);
}
void perm(char *list, int i, int n)
{
 int j, temp;
 if(i==n) {
  for(j=0; j<=n; j++)
   printf("%c",list[j]);
  printf(" ::\n");
 }
 else {
  for(j=i; j<=n; j++) {
   SWAP(list[i], list[j], temp); printf("(1)i:%d,j:%d\n",i,j);
   perm(list, i+1, n);                  printf("(2)i:%d,j:%d\n",i,j);
   SWAP(list[i], list[j], temp); printf("(3)i:%d,j:%d\n",i,j);
  }
 }
}

자 그럼 소스를 보시라 메인함수에선

char list[3] = {a, b, c};   // 배열선언, a,b,c 값을 넣었다.

perm(list, 0, 2);              // 자료구조책에 나온데로 perm(list, 0, n-1)대로 호출

첫번째호출상태 perm(list, 0, 2) 호출

if(i==n) 여기서 i=0, n=2 다르므로 통과하여 else로 간다.

for문에서 처음으로 SWAP을 만나는데 i와 j가 0으로 같으므로 배열엔 변화없다.

(왼쪽 그림1 은 위 소스를 실행한 결과다.)

그리고 확인차 심어논 (1)번 printf문에도 (왼쪽 그림을 보시라)

(1) i:0,j:0 출력. 이어서

두번째호출상태 perm(list, i+1, n)의해

perm(list, 1, 2)가 호출된다. 들어가자마자 만나는 if(i==n)에서 역시 i=1, n=2이므로 통과하여 else로 간다. 역시 for문에서 SWAP문을 만나는데 i와 j가 1로 같으므로 배열엔 변화없다. (1) i:1,j:1 출력 이어서

세번째호출상태

perm(list, 2, 2)가 호출된다. 들어가자마자 만나는 if(i==n)에서 이번엔

i=2, n=2로 같으므로 현재의 배열상태 abc 출력 ( :: 이건 구분선)

그리고 함수에서 빠져나오자마자

두번째호출상태

확인차 (2) i:1,j:1 출력 이어서 아래 SWAP i=j 이므로 역시배열에 아무변화 없음. 그리고 확인출력 (3) i:1,j:1 그리고 for문을돈다

for문에의해 i값은 변화없고 j값은 2가된다. 이어서 SWAP(1, 2)를 실행하면 배열은 {a, c, b}로 바뀐다. 확인출력 (1) i:1, j:2 바로

세번째호출상태

perm(2, 2)가 출력되어 현재의 배열상태인 acb 가 출력된다. 함수에서 나와서

두번째호출상태

확인출력 (2) i:1, j:2 다음 SWAP문에서 배열의 {a, b, c}로 바뀐다. 확인출력 (3) i:1, j:2 j=n=2이므로 for문에서나와 함수에서나와

첫번째호출상태

확인출력 (2) i=0,j=0 SWAP문을 만나는데 i=j=0으로 배열에 변화 없다. 확인출력 (3) i=0,j=0 그리고 for문을 돈다 for문에의해 i값은 변화없고 j값은 1이된다. SWAP(0, 1)에의해 배열은 {b, a, c}로 바꼈다. 확인출력 (1) i:0, j:1 그리고

두번째호출상태

perm(1,2) 호출 if(i==n) 여기서 i=1, n=2 다르므로 통과하여 else로 SWAP을만나도 i=j=1로 같으므로 배열에 변화없음 확인출력 (1) i:1, j:1 또

세번째호출상태

perm(2,2) 호출 i=n=2로 같으므로 현재 배열상태인 bac 출력. 함수를 나와서

두번째호출상태

확인출력 (2) i:1, j;1 SWAP문에선 i=j=1 이므로

배열에 변화없고 확인출력 (3) i:1, j:1

그리고 for문을 돈다 i는 변화없고 j는 2가되어 SWAP(1, 2) 에서 배열은 {b, c, a}가 된다. 확인출력 (1) i:1, j:2 그리고

세번째호출상태

perm(2,2) 호출 i=n=2로 같으므로 현재 배열상태인 bca 출력. 함수를 나와서

두번째호출상태

확인출력 (2) i:1, j:2 SWAP(1, 2) 실행. 배열은 {b, a, c}로 바뀐다. 확인출력 (3) i:1, j:2 j=2 이므로 for문종료 함수를 나온다

첫번째호출상태

확인출력 (2) i:0, j:1 SWAP(0, 1) 실행. 배열은 {a, b, c}로 바뀐다. 확인출력 (3) i:0, j:1

아직 j<2이므로 for문을 돈다. SWAP(0, 2) 실행. 배열은 {c, b, a}가 된다. 확인출력 (1) i:0, j:2

두번째호출상태

perm(1, 2) 호출 SWAP(1, 1) 실행. 배열변화없음. 확인출력 (1) i:1, j:1

세번재호출상태

perm(2, 2) 호출  i=j=2 이므로 현재 배열상태인 cba 출력. 함수를 나와서

두번째호출상태

확인출력 (2) i:1, j:1 SWAP(1, 1) 실행. 배열에 변화없음. 확인출력 (3) i:1, j:1 j<2이므로

for문을 돈다. SWAP(1, 2) 실행. 배열은 {c, a, b}가 된다. 확인출력 (1) i:1, j:2 

세번째호출상태

perm(2, 2) 호출 i=j=2 이므로 현재 배열상태인 cab 출력. 함수을 나와서

두번째호출상태

확인출력 (2) i:1, j:2 SWAP(1, 2) 실행. 배열은 {c, b, a} 가 된다. 확인출력 (3) i:1, j:2

j=2이므로 for문 종료 함수를 나와서

첫번째호출상태   

확인출력 (2) i:0, j:2 SWAP(0, 2) 실행. 배열은 {a, b, c}가 된다. 확인출력 (3) i:0, j:2

j=2이므로 for문종료. perm()함수종료. 프로그램 종료.

호출패턴은 첫 - 두 - 세(abc) - 두 - 세(acb) - 두

             첫 - 두 - 세(bac) - 두 - 세(bca) - 두

             첫 - 두 - 세(cba) - 두 - 세(cab) - 두 - 첫 이다.

여섯번의 '세'에서만 배열출력이 일어난다. 믿기싫지만 이것도 다 의도해서 코딩한것이겠지 T.T

어떤요소가 이런 패턴을 만드는지, 언제쯤 이면 나도 recursive pattern을 자유자재로 다룰수 있을것인가...지금은 복학전이라 이런 짧은 코드에도 당황하지만 더 수련을 쌓아서 척보면 알수있도록 하리라...아자아자아자!!!!!