C++로 문자 반복을 허용하는 문자열의 모든 순열 출력하기

이 문제에서는 n개의 문자로 구성된 문자열이 주어지며, 해당 문자열의 문자들을 조합해 만들 수 있는 모든 순열(permutation)을 출력해야 합니다. 이때 각 문자의 중복 사용(반복)이 허용됩니다. 또한 순열은 반드시 알파벳 순서(사전순, lexicographical order)대로 정렬하여 출력해야 합니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

입력 − XY

출력 − XX, XY, YX, YY

접근 방법 : 고정 후 재귀(Fix and Recur) 논리

이 문제를 해결하려면 '고정 후 재귀(fix and recur)' 기법을 활용해야 합니다. 먼저 배열의 첫 번째 인덱스에 한 문자를 고정한 뒤, 나머지 위치에 들어갈 문자들에 대해 같은 함수를 재귀적으로 호출하는 방식입니다.

단계별 동작 과정

입력 문자열이 "XY"일 때의 진행 과정을 살펴보겠습니다.

1. 첫 번째 인덱스에 'X'를 고정합니다 : X_

2. 재귀 호출을 통해 나머지 자리를 채웁니다 : XX → XY

3. 이번에는 첫 번째 인덱스에 'Y'를 고정합니다 : Y_

4. 재귀 호출을 통해 나머지 자리를 채웁니다 : YX → YY

위 논리는 길이가 3, 4, 그리고 일반적인 n인 문자열에도 동일하게 적용할 수 있습니다.

구현 예제

#include <iostream>
#include<string.h>
using namespace std;
void printPermutations(char *str, char* permutations, int last, int index){
    int i, len = strlen(str);
    for ( i = 0; i < len; i++ ) {
        permutations[index] = str[i] ;
        if (index == last)
            cout<<permutations <<"	";
        else
            printPermutations (str, permutations, last, index+1);
    }
}
int main() {
    char str[] = "ABC";
    cout<<"All permutations of the string with repetition of "<<str<<" are: "<<endl ;
    int len = strlen(str) ;
    char permutations[len];
    printPermutations (str, permutations, len-1, 0);
    return 0;
}

출력 결과

All permutations of the string with repetition of ABC are:
AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

복잡도 분석

길이가 n인 문자열에서 각 위치마다 n개의 문자를 선택할 수 있으므로, 생성되는 순열의 총 개수는 nⁿ개입니다. 따라서 이 알고리즘의 시간 복잡도는 O(nⁿ)이며, 입력 크기가 커질수록 출력량이 지수적으로 증가한다는 점을 유의해야 합니다.