C++로 문자열의 n번째 사전식 순열 효율적으로 구하기

개념

소문자 알파벳으로만 구성된 길이 m의 문자열이 주어졌을 때, 이 문자열의 모든 순열을 사전식(lexicographic) 순서로 정렬했을 때의 n번째 순열을 구하는 것이 이 문제의 목표입니다.

예제 1

입력:

str[] = "pqr", n = 3

출력:

Result = "qpr"

설명: 사전순으로 정렬된 모든 순열은 pqr, prq, qpr, qrp, rpq, rqp이며, 세 번째 순열은 "qpr"입니다.

예제 2

입력:

str[] = "xyx", n = 2

출력:

Result = "xyx"

설명: 사전순으로 정렬된 모든 순열은 xxy, xyx, yxx이며, 두 번째 순열은 "xyx"입니다.

접근 방법

모든 순열을 일일이 생성하는 것은 매우 비효율적입니다. 대신 수학적 성질을 활용하면 원하는 순열만 정확하게 찾아낼 수 있습니다. 이 접근법의 핵심이 되는 세 가지 사실은 다음과 같습니다.

N개의 서로 다른 문자로 만들 수 있는 순열의 총 개수는 N!입니다.
문자에 중복이 있는 경우, 즉 문자 C1이 M1번, C2가 M2번, ..., Ck가 Mk번 등장한다면 순열의 총 개수는 N!/(M1! × M2! × ... × Mk!)입니다.
첫 번째 자리에 올 문자를 하나 고정하면, 나머지 문자들로 만들 수 있는 순열의 개수를 위 공식으로 미리 계산해 둘 수 있습니다.

알고리즘 단계

먼저 freq[] 배열에 문자열에 등장하는 모든 문자의 빈도를 기록합니다.
빈도가 0보다 큰 가장 작은 문자부터 차례대로 살펴보며, 해당 문자를 첫 글자로 고정했을 때 만들 수 있는 순열의 최대 개수를 계산합니다.
누적 개수가 주어진 n보다 크거나 같으면 그 문자를 결과의 첫 글자로 확정하고, freq[i]를 1 감소시킨 뒤 나머지 자리에 대해 동일한 과정을 반복합니다.
반대로 누적 개수가 n보다 작으면 빈도표에서 다음 문자로 넘어가면서, n을 넘는 문자를 찾을 때까지 누적 개수를 계속 갱신합니다.

이 방법의 시간 복잡도는 대략 O(n) 수준으로, 문자열의 길이에 비례합니다. 참고로 코드에서는 팩토리얼을 20!까지만 미리 계산하므로, 이보다 큰 값이 필요한 경우 임의 정밀도 정수 처리가 필요합니다.

C++ 구현 예제

// n번째 순열을 출력하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX_CHAR1 = 26;
const int MAX_FACT1 = 20;
ll fact1[MAX_FACT1];

// 팩토리얼 값을 미리 계산하는 유틸리티 함수
void precomputeFactorials(){
    fact1[0] = 1;
    for (int i = 1; i < MAX_FACT1; i++)
        fact1[i] = fact1[i - 1] * i;
}

// n번째 순열을 구하는 함수
void nPermute(char str1[], int n1){
    precomputeFactorials();
    // 주어진 문자열의 길이
    int len1 = strlen(str1);
    // 모든 문자의 빈도를 계산
    int freq1[MAX_CHAR1] = { 0 };
    for (int i = 0; i < len1; i++)
        freq1[str1[i] - 'a']++;
    // 출력 문자열을 담을 배열
    char out1[MAX_CHAR1];
    // 합이 n1과 같아질 때까지 반복
    int sum1 = 0;
    int k1 = 0;
    // 이 루프에서 n1과 sum1을 갱신합니다.
    while (sum1 != n1) {
        sum1 = 0;
        // freq1[]에 존재하는 문자를 검사
        for (int i = 0; i < MAX_CHAR1; i++) {
            if (freq1[i] == 0)
                continue;
            // 문자 하나를 제거
            freq1[i]--;
            // 특정 문자를 고정한 후의 순열 개수 계산
            int xsum1 = fact1[len1 - 1 - k1];
            for (int j = 0; j < MAX_CHAR1; j++)
                xsum1 /= fact1[freq1[j]];
            sum1 += xsum1;
            // sum1 >= n1이면 해당 문자를 현재 자리에 고정하고
            // n1과 sum1을 갱신
            if (sum1 >= n1) {
                out1[k1++] = i + 'a';
                n1 -= (sum1 - xsum1);
                break;
            }
            // sum1 < n1이면 문자를 다시 되돌림
            if (sum1 < n1)
                freq1[i]++;
        }
    }
    // sum1 == n1인 경우, 남은 문자들을 내림차순으로
    // 배치하면 그것이 곧 n번째 순열이 됩니다.
    for (int i = MAX_CHAR1 - 1;
         k1 < len1 && i >= 0; i--)
        if (freq1[i]) {
            out1[k1++] = i + 'a';
            freq1[i++]--;
        }
    // 문자열 종료 문자를 붙이고 결과 출력
    out1[k1] = '\0';
    cout << out1;
}

// 드라이버 코드
int main(){
    int n1 = 5;
    char str1[] = "tutorialspoint";
    // int n1 = 3;
    // char str1[] = "pqr";
    // int n1 = 2;
    // char str1[] = "xyx";
    nPermute(str1, n1);
    return 0;
}

위 예제 코드는 문자열 "tutorialspoint"의 다섯 번째 사전식 순열을 구합니다. 주석 처리된 부분의 입력값으로 바꾸면 앞서 살펴본 예제들도 동일하게 테스트할 수 있습니다.

실행 결과

aiilnooprtsttu