Open2021/04/24にコメント追加2

"ABC" と {'A', 'B', 'C'}

AAA, AAB, AAC, ABA, ABB, ...

みたいな記号の組み合わせを出力する方法を考えいたときに、再帰関数を適当に実装していたら、なんかおかしなことになった。

(1)最初の実装

#include <bits/stdc++.h>
using namespace std;

void buildArr(set<string> &res, const string& buf, int limit) {
    if (buf.length() == limit) {
        res.insert(buf);
        return;
    }
    for (char c: "ABC") {
        buildArr(res, buf + c, limit);
    }
}

int main() {

    int N = 3;
    set<string> res;
    buildArr(res, "",  N);
    
    // print each str
    for (const auto& s: res) {
        cout << s << endl;
    }

    return 0;
}

(2)修正後

#include <bits/stdc++.h>
using namespace std;

void buildArr(set<string> &res, const string& buf, int limit) {
    if (buf.length() == limit) {
        res.insert(buf);
        return;
    }
    for (char c: {'A', 'B', 'C'}) {
        buildArr(res, buf + c, limit);
    }
}

int main() {

    int N = 3;
    set<string> res;
    buildArr(res, "",  N);
    
    // print each str
    for (const auto& s: res) {
        cout << s << endl;
    }

    return 0;
}

気になった点

(1)だと長さ3ではない文字列まで拾ってしまっている。

for (char c: "ABC")

という書き方に問題が有ると思われるけど、原因はまだわからない

log5

デバッガで確認すると、(1)のケースで、2文字なのに長さ3という扱いを受ける場合がある模様