순열?

수학에서 순열을 공부해 본 기억은 있지만 당체 생각이 나지 않는다, 다만 순열과 조합의 개념을 이용한 알고리즘 문제는 굉장히 많다.

# 순열

보통 4H3 이런식으로 표기하는데 4개의 숫자 중 3개를 선택해서 나타낼 수 있는 모든 수열이 되겠다.(중복 포함)

계산은 4 X 3 X 2 = 24가지 인데 어떤 수열이 나오는지 보자.

1, 2, 3, 4 중에 3가지 숫자를 뽑아서 만들어 보면 진짜 24개가 나온다.

123 124 132 134 142 143 

213 214 231 234 241 243

312 314 321 324 341 342

412 413 421 423 431 432

3개의 숫자를 뽑을때 중복을 허용한다는 의미는 같은 숫자를 뽑을 수 있다는게 아니라, 123, 132 같이 숫자를 같은 거를 뽑았으나 위치가 하나라도 다르면 다른 경우로 판단한다는 뜻이다.

잘 들여다 보면 규칙성이 살짝 보이기 시작한다.

맨 앞의 숫자가 1에서 마지막엔 4로 시작되는 수열이 등장한다. 먼가 차례차례 바꿔서 바꿀 수 있는 모든 경우가 끝나면 다음 자리의 수의 바꾸고 똑같은 바꿈을 반복수행한다. 다시 설명하면,

1 2 3 이 등장한다. 지금 남은 카드는 4이므로 마지막 자리숫자를 바꾸면 새로운 경우수가 된다. 1 2 4.

마지막 자리의 숫자를 바꾸는 경우는 다 사용했다면 이제 두번째 자리의 숫자를 바꾼다. 그때는 다시 1 2 3 에서 생각해보면 1 3 2 이다. 이 때도 역시 다음 카드는 4이다. 그럼 아래 같이 바꾸는 게 가능하다. 

1 2 3 -> 1 2 4

1 3 2 -> 1 3 4

두번째 자리의 숫자는 2, 3 만 쓰였으므로 4가 올 수 있는 경우가 있다.

1 4 2 -> 1 4 3

중복으로 2개의 숫자를 같게 쓸수 없으나, 맨 앞자리 1이 오는 경우 두번째 세번째 자리의 숫자가 바뀌는 경우는 위와 같이 6가지가 된다.

동일하게 2로 시작하는 경우도 6가지, 3으로 해도 6가지, 4로해도 6가지가 나오는 것이다.

근데 이걸 어떻게 코딩으로 옮길까?

기본적으로 규칙성이 있다면 재귀를 사용하는 것이 좋으며 재귀를 사용헐 때는 꼭 종료조건을 주어 끝이나야 한다. 만약 순열을 재귀로 구현한다면 종료조건은 무엇이되어야할까?

그렇다 바로 3가지 숫자를 선택했다면. 이 종료조건이 된다, 간단한 코드로 나타내면

void perm(int n, int r, int depth){

  if( 종료조건){

     //print All;

return;

  }

  //카드 고르고

   perm(n, r, depth+1);

}

int main(void)

{

    perm(4, 3, 0); //n, r, depth

    return 0;

}

여기까지 이해했다면 다 왔다, 방금 말한대로 종료조건에 다다르면 출력하고 리턴해주고, 종료조건이 아니면 자기 자신을 부른다. 단, 어떤 배열에 자신을 넣어야, 그 배열의 값을 출력할 것이나, 아래와 같이 코드를 구현한다.

void printAll(int total) {

for (int i = 0; i < total; ++i) {

printf("%d ", result[i]);

}

printf("\n");

}

void perm(int n, int r, int depth) {

if (depth == r) {

printAll(r);

}

for (int i = 0; i < n; ++i) {

if (visited[i] != 1) {

visited[i] = 1;

result[depth] = i + 1;

perm(n, r, depth + 1);

result[depth] = 0;

visited[i] = 0;

}

}

}

int main(void)

{

int n = 4;

int r = 3;

perm(n, r, 0);

return 0;

}

여기서 중요한건 visited라는 녀석이다. visited의 역할은 result 라는 배열에 카드를 뽑아 depth라는 녀석을 index로 활용하여 저장하게 되는데, 첫번째, 두번째 카드가 정해져서 result 배열에 담아졌다면 다시 담을 필요없이 세번째 카드만 저앻지면 된다. 그리고 만약 n 까지 확인해서 카드를 다 사용했다면 2번째 자리의 카드를 바꿔서 다시 동일하게 반복해야 하는데, 일반적으로 이부분이 이해하는데 어려움을 겪곤 한다. 

출처 : http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/

위 그림을 보면 조금 더 이해 할 수 있지 않을까 생각 되면서도 백프로 이해되게 설명하지 못하는 사실이 안타깝다.:D 그럼 다음 글에서 문제로 만나보자!