C++ STL로 배열의 모든 역순열(내림차순 순열) 생성하기

이 글에서는 C++의 STL(표준 템플릿 라이브러리)을 활용하여 배열의 모든 역순열, 즉 내림차순 기준으로 정렬된 순열을 생성하는 방법을 알아봅니다.

예를 들어 (1, 2, 3)이라는 세 개의 숫자가 있을 때, 일반적인 순열(오름차순 순열)과 역순열은 각각 다음과 같이 출력됩니다.

일반 순열 (Forward Permutation)

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

역순열 (Reversed Permutation)

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

역순열을 구하려면 STL에서 제공하는 prev_permutation() 함수를 사용합니다. 이 함수는 현재 배열을 사전적으로 이전 순서(내림차순 방향)의 순열로 변환하며, 더 이상 이전 순열이 존재하지 않으면 false를 반환합니다.

알고리즘

getPermutation(arr, n)

시작
    배열 arr을 오름차순으로 정렬한다
    배열 arr을 뒤집어 내림차순으로 만든다
    반복:
        배열의 원소들을 출력한다
    prev_permutation 계산이 끝날 때까지 반복한다
종료

핵심 포인트는 배열을 먼저 내림차순으로 정렬한 상태에서 시작해야 한다는 것입니다. prev_permutation()은 사전적 순서 기준으로 '이전' 순열을 찾기 때문에, 가장 큰 순열(내림차순 정렬 상태)부터 시작해야 모든 순열을 빠짐없이 생성할 수 있습니다.

예제 코드

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

void disp(int arr[], int n){
    for(int i = 0; i<n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

void getPermutation(int arr[], int n) {
    sort(arr, arr + n);   // 오름차순 정렬
    reverse(arr, arr+n);  // 내림차순으로 뒤집기
    cout << "Possible permutations: \n";
    do{
        disp(arr, n);
    }while(prev_permutation(arr, arr+n));
}

int main() {
    int arr[] = {11, 22, 33, 44};
    int n = sizeof(arr) / sizeof(arr[0]);
    getPermutation(arr, n);
}

실행 결과

Possible permutations:
44 33 22 11
44 33 11 22
44 22 33 11
44 22 11 33
44 11 33 22
44 11 22 33
33 44 22 11
33 44 11 22
33 22 44 11
33 22 11 44
33 11 44 22
33 11 22 44
22 44 33 11
22 44 11 33
22 33 44 11
22 33 11 44
22 11 44 33
22 11 33 44
11 44 33 22
11 44 22 33
11 33 44 22
11 33 22 44
11 22 44 33
11 22 33 44

위 출력 결과를 보면 가장 큰 값부터 시작하여 사전적 역순으로 모든 순열이 차례대로 생성되는 것을 확인할 수 있습니다. 참고로 원소가 n개인 배열의 순열 개수는 n!개이므로, 위 예제의 4개 원소에 대해 총 24가지(4! = 24)의 순열이 출력됩니다.