순열 (Permutation) - 교환방식

- 순열 (Permutation) -

 

n개의 수를 중복을 허용하지 않고(visited)

r개를 나열할 수 있는 모든 경우의 수 (1 ≤ r ≤ n)

 

---

 

문제인식)

1부터 3(n)까지의 수가 있다.
이들을 이용하여 3(r)개의 수를 중복없이 나열하고자 할 때
가능한 모든 경우를 각각 한 줄씩 출력하고자 한다면 어떻게 해야할까?

int n=3, r=3;

 

해결과정)

1) 현재위치(dpth)와 맞바꿀 위치(i)간에 swap을 진행한다. dpth는 재귀의 깊이이자 맞바꿀 위치의 시작.

2) 맞바꿀 위치(dpth)를 옮기기위해 다음 위치(dpth+1)로 재귀적 진입을 한다.

3) 깊은재귀가 끝나면 윈위치시킨다.(다시 swap)

 

(※ [더보기]를 클릭하면 C/C++ 소스코드를 참조할 수 있습니다.)

#include<iostream>
#include<vector>
using namespace std;

int n=3, r=3;
vector<int> v;

void Permutation(int r, int dpth) {
    if(dpth>=r) {
        //출력 
        for(int i=0; i<r; i++) printf("%d ", v[i]); printf("\n");
        //종료 
        return;
    }

    for(int i=dpth; i<n; i++) { //i는 swap을 진행하기 위한 인덱스 
        swap(v[i], v[dpth]);
        Permutation(r, dpth+1); //재귀진입
        swap(v[i], v[dpth]);
    }
}

int main() {
    //수를 vector에 삽입
    for(int i=1; i<=n; i++) v.push_back(i);

    Permutation(r, 0);

    return 0;
}

위 코드의 경우 시간복잡도는 당연히 O(n의 r제곱)이다.

 

주의점)

사실 이 방식은 오름차순으로 탐색이 되지 않는다.

위 그림에서도 보듯이 dpth가 1이될 때 3번째 그림은,

0과 2의 자리를 맞바꾸었기 때문에 "3 2 1 "이 되었다.

정상적인 순서라면 "3 1 2 "가 맞아야하는데 그 순서가 어긋났다.

 

이런 이유로 실제로 교환방식을 사용하는 것은

개인적으로 권장하지 않는다.

 

그러나 next_permutation(), prev_permutation() 함수는

swap방식인데도 오름차순, 내림차순 순서를 보장한다! (필자도 솔직히 어떻게 보장되는진 아직 모른다.)

이 두 함수에 대한 자세한 설명은 여기를 참조

 

응용)

수를 재귀적으로 위치를 맞바꾸는 방식이 아닌, 재귀적으로 삽입하는 방식으로 해보기

 

등