Brute Force: 순열/팩토리얼

이 또한 방학 때 교수님께서 알려주신 알고리즘으로, 모든 가능한 순열을 생성해본다.

 

https://yunjae-gong.tistory.com/29

Brute Force: 조합

조합 알고리즘은 i번째 원소로 n을 채택할지 하지 않을지 재귀적으로 함수를 호출해 해결했다.

 

순열 알고리즘의 경우, N개중 K개를 뽑아 나열해야 하므로, 추가로 각 원소의 위치를 바꿔주는 동작이 추가된다.

 

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void Permutation_2(int P[],int i, int k) { // top down
    for(int j=i;j<=N;++j) { // j번째부터 시작
        swap(P[i],P[j]);
        if(i == k) { // i가 k이면 nPk 완성
            for(int l=1;l<=k;++l)
                printf("%c ",P[l]);
            printf("\n");
        } // 출력
        Permutation_2(P,i+1,k);
        swap(P[i],P[j]); // 원래 상태로 만들어야 이후 j+1번째부터 시작하는 순열 생성 가능
    }
}

int main() {
    int k;
    scanf("%d%d",&N,&k); // nPk
    int P[N+1];
    for(int i=0;i<N;++i)
        P[i+1] = 'a'+i;
    Permutation_2(P,1,k); // top down
}

코드를 짠지 꽤 오랜 시간이 지나, 어떻게 동작했는지 잘 이해가 안갔는데 다음 방법으로 접근했을 때 이해가 조금 쉬웠다.

 

이 알고리즘은 호출될 때마다 i가 1씩 증가한다. K=4를 가정할 때, 4번 호출된 상태(마지막 남은 원소 하나를 선택할 때)라고 하자.

i는 4이고, 따라서 for loop의 j는 i(4)부터 시작한다. 4부터 N 사이에 있는 수 중, 하나를 선택하고, i위치(i번째 원소로 P[j]를 선택)와 j위치를 swap한다.

 

여기서 swap은 i번째 원소로 j번째 원소를 사용하겠다는 뜻으로, swap 과정을 통해 서로 다른 순서로 뒤섞임이 발생한다.

k는 K일 때의 for loop가 종료되면 k = K-1일 때 위 동작을 반복함을 생각하면, 예시 코드가 어떤 동작으로 이해하기 편리할 것이다.