In tất cả câu có thể tạo từ danh sách từ bằng đệ quy C++

Cho danh sách các danh sách từ (vector>). Tạo tất cả câu bằng cách chọn đúng 1 từ từ mỗi danh sách theo thứ tự, dùng đệ quy.

Ví dụ

Input: {{"I", "You"}, {"Do", "like"}, {"walking", "eating"}}
Output:
I Do walking
I Do eating
I like walking
I like eating
You Do walking
You Do eating
You like walking
You like eating

Phương pháp đệ quy

Hàm đệ quy recurse(level, current_sentence):

• Nếu level == số danh sách: in current_sentence.
• Ngược lại: duyệt qua từ trong danh sách level, thêm vào câu, gọi đệ quy level+1.

Mã nguồn C++

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

void generateSentences(vector<vector<string>> &lists, int level, vector<string> &current) {
    if (level == lists.size()) {
        for (string &w : current) cout << w << " ";
        cout << "\n";
        return;
    }
    for (string &word : lists[level]) {
        current.push_back(word);
        generateSentences(lists, level + 1, current);
        current.pop_back();
    }
}

int main() {
    vector<vector<string>> lists = {
        {"Ajay", "Sanjay"},
        {"Like", "is"},
        {"Reading", "eating"}
    };
    vector<string> current;
    generateSentences(lists, 0, current);
    return 0;
}

Kết quả

Ajay Like Reading
Ajay Like eating
Ajay is Reading
Ajay is eating
Sanjay Like Reading
Sanjay Like eating
Sanjay is Reading
Sanjay is eating

Giải thích

Backtracking cổ điển: tại mỗi cấp độ, thử từng từ, thêm vào câu hiện tại, đệ quy cấp sau, sau đó bỏ từ (backtrack). Độ phức tạp O(∏ size_of_list_i).

Kết luận

Bài viết trình bày thuật toán backtracking/đệ quy sinh tất cả câu từ danh sách từ. Mã C++ dùng vector, đệ quy đơn giản, dễ hiểu. Có thể triển khai bằng Python, Java.