이번 글에서는 주어진 문자열로 만들 수 있는 모든 길이의 문자열을 생성하는 방법을 살펴보겠습니다. 이 기법은 각 문자의 조합을 비트마스킹으로 추출한 뒤, 추출된 문자들의 순열을 모두 출력합니다. 예를 들어 입력 문자열이 ABC라면 다음과 같은 결과가 생성됩니다.
{A, B, C, AB, BA, BC, CB, CA, AC, ABC, ACB, BAC, BCA, CAB, CBA}
길이가 n인 문자열에서 만들 수 있는 부분 집합(조합)은 공집합을 제외하면 총 2n − 1개이며, 각 조합마다 가능한 모든 순열을 추가로 생성하는 것이 이 알고리즘의 핵심입니다.
알고리즘
printAllString(str)
Begin
n := 문자열 str의 길이
count := 2^n – 1
for 각 counter를 1부터 count까지 반복:
sub_str := 빈 문자열
for j를 0부터 n까지 반복:
if counter의 j번째 비트가 1이면
str의 j번째 문자를 sub_str에 추가
end if
done
repeat:
sub_str 출력
until sub_str의 다음 순열이 더 이상 없을 때까지
done
End동작 원리: 카운터(counter)의 각 비트는 문자열 내 해당 위치의 문자를 포함할지 여부를 나타냅니다. 예를 들어 n=4일 때 counter가 0101(2진수)이라면 1번째와 3번째 문자만 선택되어 부분 문자열이 만들어집니다. 이렇게 만들어진 부분 문자열에 대해 C++ 표준 라이브러리의 next_permutation() 함수를 사용해 모든 순열을 차례대로 출력합니다.
C++ 코드 예제
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
void printAllString(string str) {
int n = str.size();
unsigned int count = pow(2, n);
for (int counter = 1; counter < count; counter++) { // 2^n - 1개의 문자열 생성
string subs = "";
for (int j = 0; j < n; j++) {
if (counter & (1<<j)) // j번째 비트가 설정된 경우 j번째 문자 추가
subs.push_back(str[j]);
}
do {
cout << subs << endl;
}
while (next_permutation(subs.begin(), subs.end()));
}
}출력 결과
입력 문자열이 ABCD일 때 프로그램을 실행하면 아래와 같이 모든 조합과 그 순열이 출력됩니다.
A B AB BA C AC CA BC CB ABC ACB BAC BCA CAB CBA D AD DA BD DB ABD ADB BAD BDA DAB DBA CD DC ACD ADC CAD CDA DAC DCA BCD BDC CBD CDB DBC DCB ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
이처럼 비트 연산과 순열 생성 함수를 조합하면 주어진 문자열의 모든 길이에 대한 가능한 문자열을 효율적으로 생성할 수 있습니다. 단, 문자 개수가 늘어나면 결과의 수가 지수적으로 증가하므로(총 (2n − 1)개 조합 × 각 조합의 순열 수), 입력 문자열이 길어질 경우 출력량과 시간이 크게 늘어난다는 점을 유의해야 합니다.