Permutation 순열

안녕하세요. 문제를 풀다가 순열 관련 부분에서 머리가 터져버려(?) 순열에 대해 공부해보고자 합니다.

순열은 순서가 있는 열, 순서를 가지고 줄세우는 경우의 수 라고 생각하시면 됩니다.

1번과 2번의 사람이 있다면 이 둘을 줄세우는 경우의 수는

1, 2
2, 1

이렇게 2가지 경우가 있겠죠.

1, 2, 3 세 명의 사람이라면

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

이렇게 총 6가지 경우가 있습니다.
맨 앞 자리에 올 수 있는 사람의 수는 3
맨 앞자리가 정해졌다면 그 다음에 올 수 있는 사람의 수는 2
그 다음은 1

즉 순열의 경우의 수는 n! 이 됩니다.

여기까지는 많이들 알고계셨던 내용이겠죠? 이제 이를 코드로 구현하려면 어떻게 해야하는지 살펴보겠습니다.

오늘은 재귀를 이용해서 구해보려고 합니다.

재귀 개념이 궁금하시다면 재귀 포스팅 :)

 

앞의 예처럼 1 ~ 3까지를 줄세우는 경우 [1, 2, 3]을 가지고 살펴볼게요. 

처음 1로 시작했으면 1을 뽑고 나머지 경우 [2, 3] 에 대한 순열을 구합니다.

1, 2까지 뽑았으면 나머지 3에 대한 순열을 구합니다. 이제 3은 원소가 하나밖에 없으므로 바로 선택해서 [1, 2, 3]을 출력합니다.

 

하는 일은 

숫자를 하나 뽑고 나머지에 대한 순열을 다시 구하는 것 뿐입니다. 재귀적으로 돌고 있죠.

현재 인덱스 k를 인자로 받고 k가 끝에 도달했으면 이를 출력해주고 return하면 됩니다. 이게 기저사례가 되겠죠.

코드는 자체는 사실 간단합니다. 

func perm(_ k: Int) {
    if k == data.count {
        print(data)
        return
    }

    for i in k..<data.count {
        data.swapAt(k, i)  // swap 하면서 k를 선택한 것이 된다.
        perm(k+1)
        data.swapAt(k, i)  // 순열을 돌고나서 다시 원위치 시켜줘야한다.
    }
}

 

k까지 뽑힌 상태이므로 그 다음의 모든 경우에 대해 찾아 주기 위해서 k부터 배열의 마지막까지 for 문을 돌려주는데요,

뽑는 행위를 swap을 통해 하고 있습니다.

k와 나머지 인덱스를 바꿔주고 k+1을 인자로 다시 호출해주므로 k는 탐색이 끝난 생태가 되는거죠.

한 가지 주의할 점은 swap을 해줬으면 순열을 돌고나서 다시 제자리로 원위치 시켜줘야 합니다.

원위치 시켜주지 않고 두면 중간에 순서가 뒤죽박죽 섞이므로 모든 경우에 대한 탐색이 보장되지 않습니다.

말로 제대로 설명이 되었는지 잘 모르겠네요.. 😥

 

현재는 배열의 마지막까지 모든 경우를 다 탐색하는 경우이므로 인자를 하나만 받고 종료케이스를 배열의 마지막 인덱스로 해주었는데요,

시작과 마지막 인덱스를 받아서 처리할 수도 있습니다.

func perm(start s: Int, end e: Int) {
    if s == e {
        print(data[0..<e])
    }
    
    for i in s..<e {
        data.swapAt(s, i)
        perm(start: s+1, end: e)
        data.swapAt(s, i)
    }
}

 

조금이라도 도움이 되셨는지 모르겠네요

감사합니다 :)