อิเทอเรเตอร์สำหรับการจัดหมู่ใน C++

เราต้องออกแบบคลาส Iterator ที่มีการดำเนินการดังนี้:

• คอนสตรัคเตอร์รับสตริง characters (ตัวอักษรภาษาอังกฤษพิมพ์เล็กเรียงลำดับไม่ซ้ำ) และตัวเลข combinationLength
• ฟังก์ชัน next() คืนการจัดหมู่ (combination) ถัดไปที่มีความยาว combinationLength ตามลำดับอักษร
• ฟังก์ชัน hasNext() คืน true ก็ต่อเมื่อมีการจัดหมู่ถัดไป

ตัวอย่าง: CombinationIterator iterator = new CombinationIterator("xyz", 2);
iterator.next() คืน "xy"
iterator.hasNext() คืน true
iterator.next() คืน "xz"
iterator.hasNext() คืน true
iterator.next() คืน "yz"
iterator.hasNext() คืน false

ขั้นตอนการแก้ปัญหา (Pre-compute All Combinations)

• สร้างอาร์เรย์ combs ของสตริง และดัชนี idx
• กำหนดเมธอด makeCombs(s, l, temp="", start=0):
  • ถ้าขนาดของ temp == l ใส่ temp เข้า combs คืนค่า
  • วนลูป i จาก start ถึง ขนาดของ s:
    • เรียก makeCombs(s, l, temp + s[i], i + 1)
• คอนสตรัคเตอร์: เรียก makeCombs(c, cl) กำหนด idx := 0
• next(): เพิ่ม idx คืน combs[idx - 1]
• hasNext(): คืน true ถ้า idx != ขนาดของ combs มิฉะนั้น 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());
    }
};

int 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;
}

อินพุต

Initialize with "xyz" and 2, then call next() and hasNext() multiple times

เอาต์พุต

xy 1 xz 1 yz 0