C++で組み合わせイテレータを実装する方法

ここでは、以下のような操作を持つイテレータクラスを設計することを考えます。

• ソート済みの重複のない小文字英字からなる文字列と、数値 combinationLength を引数に取るコンストラクタを定義します。
• 辞書順において次の長さ combinationLength の組み合わせを返す next() 関数を定義します。
• 次の組み合わせが存在する場合にのみ true を返す hasNext() 関数を定義します。

使用例

たとえば、次のように入力された場合を考えてみましょう。

CombinationIterator iterator = new CombinationIterator("xyz", 2);
iterator.next(); // "xy" を返す
iterator.hasNext(); // true を返す
iterator.next(); // "xz" を返す
iterator.hasNext(); // true を返す
iterator.next(); // "yz" を返す
iterator.hasNext(); // false を返す

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• 文字列型の配列 comb とインデックス変数 idx を用意します。
• makeCombs() メソッドを定義します。このメソッドは、文字列 s、整数 l、初期値が空の文字列 temp、初期値が 0 の start を受け取ります。処理内容は以下の通りです。
  • temp のサイズが l と等しい場合、temp を comb に追加して処理を終了します。
  • i を start から s のサイズまでループさせ、makeCombs(s, l, temp + s[i], i + 1) を再帰的に呼び出します。
• printVector() メソッドは文字列配列を引数として受け取り、その要素を表示します。
• コンストラクタでは、文字列 c と整数 cl を受け取ります。
• makeCombs(c, cl) を呼び出し、idx := 0 を設定します。
• next() メソッドは idx をインクリメントし、comb[idx - 1] を返します。
• hasNext() メソッドは、idx が comb のサイズと異なる場合に true を、そうでなければ false を返します。

実装例(C++)

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class CombinationIterator {
public:
    vector <string> combs;
    int idx;
    void makeCombs(string s, int l, string temp ="", int start = 0){
        if(temp.size() == l){
            combs.push_back(temp);
            return;
        }
        for(int i = start; i < s.size(); i++){
            makeCombs(s, l, temp + s[i], i + 1);
        }
    }
    void printVector(vector <string> v){
        for(int i = 0; i < v.size(); i++){
            cout << v[i] << "\n";
        }
        cout << endl;
    }
    CombinationIterator(string c, int cl) {
        makeCombs(c, cl);
        idx = 0;
    }
    string next() {
        idx++;
        return combs[idx - 1];
    }
    bool hasNext() {
        return !(idx == combs.size());
    }
};
main(){
    CombinationIterator ob("xyz", 2);
    cout << (ob.next()) << endl;
    cout << (ob.hasNext()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext()) << endl;
    cout << (ob.next()) << endl;
    cout << (ob.hasNext()) << endl;
}

入力

"xyz" と 2 で初期化し、next() と hasNext() を複数回呼び出す

出力

xy
1
xz
1
yz
0