Bộ lặp tổ hợp trong C++

Thiết kế lớp CombinationIterator với các thao tác:

• Khởi tạo với chuỗi characters (chữ thường distinct, đã sắp xếp) và combinationLength.
• next(): trả về tổ hợp tiếp theo theo thứ tự bảng chữ cái.
• hasNext(): trả về true nếu còn tổ hợp.

Ví dụ: "xyz", length=2. Trình tự: "xy", "xz", "yz".

Giải thuật (Tiền tính tất cả tổ hợp)

1. Mảng combs lưu tất cả tổ hợp, chỉ số idx.
2. Hàm makeCombs(s, l, temp, start) đệ quy sinh tổ hợp:
3. Nếu temp.size() == l, thêm vào combs.
4. Với i từ start đến cuối, gọi đệ quy makeCombs(s, l, temp+s[i], i+1).
5. Khởi tạo: gọi makeCombs(c, cl), idx=0.
6. next(): tăng idx, trả combs[idx-1].
7. hasNext(): idx != combs.size().

Ví dụ 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);
    }
    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; // xy
    cout << ob.hasNext() << endl; // 1
    cout << ob.next() << endl; // xz
    cout << ob.hasNext() << endl; // 1
    cout << ob.next() << endl; // yz
    cout << ob.hasNext() << endl; // 0
    return 0;
}

Đầu vào

Khởi tạo "xyz" và 2, gọi next() và hasNext() nhiều lần

Đầu ra

xy 1 xz 1 yz 0