C++で文字列の全組み合わせを辞書式順序に出力する方法

この記事では、与えられた文字列 str に含まれる文字の組み合わせをすべて抽出し、辞書式順序（lexicographical order）で出力する問題をC++で解説します。

問題の概要

具体例を見てみましょう。入力として文字列「XYZ」が与えられた場合、出力は次のようになります。

Input: str = 'XYZ'
Output :
X
XY
XYZ
XZ
XZY
Y
YX
YXZ
YZ
YZX
Z
ZX
ZXY
ZY
ZYX

このように、1文字から始まり、文字列の長さ分までのすべての組み合わせがアルファベット順に並んで出力されます。

解決のアプローチ

この問題を解くには、文字列中の文字の組み合わせをすべて生成して出力する必要があります。そのために以下の工夫を行います。

• mapデータ構造の活用： 文字列の各文字とその出現回数を格納します。std::mapはキーを自動的にソートして保持するため、辞書式順序の出力に適しています。
• バックトラッキング： 再帰的に組み合わせを構築し、使用済みの文字カウントを戻しながらすべてのパターンを網羅します。

C++での実装例

以下が実際のコードです。

#include <bits/stdc++.h>
using namespace std;
void printResult(char* result, int len);
void findstringCombination(char result[], char str[], int count[], int level, int size, int length);
void printCharCombination(string str);

int main(){
    string str = "ABC";
    cout<<"The combination of characters of the string :\n";
    printCharCombination(str);
    return 0;
}

void findstringCombination(char result[], char str[], int count[], int level, int size, int length){
    if (level == size)
        return;
    for (int i = 0; i < length; i++) {
        if (count[i] == 0)
            continue;
        count[i]--;
        result[level] = str[i];
        printResult(result, level);
        findstringCombination(result, str, count, level + 1, size, length);
        count[i]++;
    }
}

void printCharCombination(string str){
    map<char, int> mp;
    for (int i = 0; i < str.size(); i++) {
        if (mp.find(str[i]) != mp.end())
            mp[str[i]] = mp[str[i]] + 1;
        else
            mp[str[i]] = 1;
    }
    char* input = new char[mp.size()];
    int* count = new int[mp.size()];
    char* result = new char[str.size()];
    map<char, int>::iterator it = mp.begin();
    int i = 0;
    for (it; it != mp.end(); it++) {
        input[i] = it->first;
        count[i] = it->second;
        i++;
    }
    int length = mp.size();
    int size = str.size();
    findstringCombination(result, input, count, 0, size, length);
}

void printResult(char* result, int len){
    for (int i = 0; i <= len; i++)
        cout<<result[i];
    cout<<endl;
}

コードのポイント

• printCharCombination関数では、まずmap<char, int>を使って各文字の出現回数をカウントします。これにより重複文字にも対応できます。
• findstringCombination関数がバックトラッキングの中核です。レベルごとに未使用の文字を選び、結果を出力した後に再帰呼び出しを行い、最後にカウントを復元（バックトラック）します。
• printResult関数は、現在構築中の部分文字列を出力します。

実行結果

入力「ABC」に対するプログラムの出力は以下の通りです。

The combination of characters of the string −
A
AB
ABC
AC
ACB
B
BA
BAC
BC
BCA
C
CA
CAB
CB
CBA

まとめ

本記事では、C++のstd::mapとバックトラッキングを組み合わせることで、文字列のすべての組み合わせを辞書式順序で効率的に出力する方法を紹介しました。mapがキーを自動ソートする特性により、特別なソート処理を追加することなく自然な順序で出力できるのがポイントです。重複する文字を含む文字列にも対応できる汎用的な実装となっています。