C++でn文字の集合から生成できる長さkのすべての文字列を出力する方法

問題概要

この問題では、文字の集合と正整数 k が与えられます。求められているのは、その集合に含まれる文字だけを使って生成できる、長さ k のすべての文字列を出力することです。

入出力例

Input: set = {'x', 'y', 'z'} , k = 2
Output: xx, xy, xz, yx, yy, yz, zx, zy, zz

解法のアプローチ

この問題を解くには、生成可能なすべての文字列を網羅的に見つける必要があります。

サイズ n の集合から作れる長さ k の文字列の総数は n^k 個になります。これは、各文字位置ごとに集合内の任意の文字を選べるためです。

この問題は再帰呼び出しを使うことでシンプルに実装できます。基本的な考え方は次の通りです。

• 空文字列からスタートする
• 現在の文字列の末尾に、集合内の各文字を順に1つずつ追加する
• 文字列の長さが k に達した時点で、その文字列を出力する

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void printKLengthString(char set[], string sequence, int n, int k) {
    if (k == 0){
        cout<<sequence<<"\t";
        return;
    }
    for (int i = 0; i < n; i++){
        string newSequence;
        newSequence=sequence+set[i];
        printKLengthString(set, newSequence, n, k - 1);
    }
}
int main() {
    char set[] = {'a', 'b'};
    int n = 2;
    int k = 3;
    printKLengthString(set, "", n, k);
}

出力結果

aaa aab aba abb baa bab bba bbb

処理の流れの解説

上記のコードでは、関数 printKLengthString が再帰的に呼び出されます。引数 k が 0 になったとき、すなわち目的の長さの文字列が完成したタイミングで、その文字列を出力して再帰を終了します。

k がまだ 0 でない場合は、for ループによって集合内の各文字を現在の文字列の末尾に追加し、残りの長さ（k - 1）を指定して自分自身を再度呼び出します。これにより、すべての組み合わせが系統的に探索されます。

例えば、集合 {a, b} から長さ 3 の文字列を生成する場合、2³ = 8 通りの組み合わせ（aaa, aab, aba, abb, baa, bab, bba, bbb）が漏れなく出力されます。

計算量について

このアルゴリズムの時間計算量は O(n^k) です。生成すべき文字列の総数そのものが n^k 個であるため、これは漸近的には最適な計算量と言えます。ただし、k や n が大きくなると組み合わせの数が爆発的に増えるため、実際の利用場面では入力サイズに注意が必要です。