Trình lặp lại để kết hợp trong C ++

Giả sử chúng ta phải thiết kế một lớp Iterator, bao gồm một vài thao tác -

• Xác định một hàm tạo nhận một chuỗi ký tự gồm các chữ cái tiếng Anh viết thường riêng biệt được sắp xếp và một tổ hợp sốLength làm tham số.
• Xác định một hàm next () trả về kết hợp tiếp theo của kết hợp độ dài Độ dài theo thứ tự bảng chữ cái.
• Xác định một hàm hasNext () khác trả về True nếu và chỉ khi tồn tại một kết hợp tiếp theo.

Vì vậy, nếu đầu vào giống như -

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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một lược mảng gồm các chuỗi và lập chỉ mục idx
• Xác định phương thức makeCombs (), phương thức này sẽ nhận chuỗi s, biến số nguyên l, một chuỗi tạm thời, ban đầu trống và bắt đầu, giá trị ban đầu là 0. Điều này được định nghĩa như sau -
• nếu kích thước của temp =l, sau đó chèn nhiệt độ vào lược và quay lại
• đối với tôi trong phạm vi bắt đầu có kích thước là s
  • makeCombs (s, l, temp + s [i], i + 1)
Phương thức
• printVector () sẽ lấy mảng của chuỗi làm đầu vào, điều này sẽ hiển thị các phần tử của mảng đó
• Xác định hàm tạo như sau:hàm này sẽ nhận chuỗi c và cl,
• gọi makeCombs (c, cl), đặt idx:=0
• Phương thức next () sẽ tăng idx và trả về comb [idx - 1]
• phương thức hasNext () sẽ trả về true nếu idx không giống với kích thước của comb, ngược lại là false.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

xy
1
xz
1
yz
0