Bài toán Đảo chữ cái

Bài toán – Đảo chữ cái

Bạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái.

Ví dụ: Cho từ “abc”, chương trình của bạn phải đưa ra được các từ “abc”, “acb”, “bac”, “bca”, “cab” và “cba” (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho).

Input. Dữ liệu vào được cho trong tệp input.txt chứa một số từ. Dòng đầu tiên là một số tự nhiên cho biết số từ được cho ở dưới. Mỗi dòng tiếp theo chứa một từ. Trong đó, một từ có thể chứa cả chữ cái thường hoặc hoa từ A đến Z. Các chữ thường và hoa được coi như là khác nhau. Một chữ cái nào đó có thể xuất hiện nhiều hơn một lần.

Output. Với mỗi từ đã cho trong file Input.txt, kết quả nhận được ra file Output.txt phải chứa tất cả các từ khác nhau  được sinh từ các chữ cái của từ đó. Các từ được sinh ra từ một từ đã cho phải được đưa ra theo thứ tự tăng dần của bảng chữ cái.

Cài đặt bài toán với Python

def generate_permutations(word, used, current, result):
    if len(current) == len(word):
        result.append(current)
        return
    for i in range(len(word)):
        if not used[i]:
            used[i] = True
            generate_permutations(word, used, current + word[i], result)
            used[i] = False

with open("input.txt", "r") as f_input, open("output.txt", "w") as f_output:
    n = int(f_input.readline().strip())
    for i in range(n):
        word = f_input.readline().strip()
        used = [False] * len(word)
        result = []
        generate_permutations(word, used, "", result)
        result.sort()
        for j in range(len(result)):
            f_output.write(result[j] + "\n")

Trong đó, hàm generate_permutations nhận vào 4 tham số: từ đã cho word, mảng boolean used để đánh dấu các chữ cái đã được sử dụng, chuỗi current để lưu trữ hoán vị hiện tại, và mảng result để lưu trữ kết quả.

Nếu độ dài của current bằng độ dài của word, chúng ta đã tìm được một hoán vị mới và thêm nó vào mảng kết quả.

Trong trường hợp khác, chúng ta sử dụng một vòng lặp để thử tất cả các chữ cái trong từ word. Nếu chữ cái tại vị trí i chưa được sử dụng, chúng ta đánh dấu nó đã được sử dụng và tiếp tục đệ quy với các giá trị mới của used và current. Sau đó, chúng ta đánh dấu lại chữ cái tại vị trí i đã không được sử dụng.

Cuối cùng, chúng ta đọc dữ liệu từ tệp input.txt, tìm hoán vị cho từng từ và ghi kết quả vào tệp output.txt.

Cài đặt bài toán với C++

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;

void generate_permutations(string word, bool used[], string current, vector<string>& result) {
    if (current.length() == word.length()) {
        result.push_back(current);
        return;
    }
    for (int i = 0; i < word.length(); i++) {
        if (!used[i]) {
            used[i] = true;
            generate_permutations(word, used, current + word[i], result);
            used[i] = false;
        }
    }
}

int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    int n;
    fin >> n;

    for (int i = 0; i < n; i++) {
        string word;
        fin >> word;
        bool used[word.length()] = {false};
        vector<string> result;
        generate_permutations(word, used, "", result);
        sort(result.begin(), result.end());
        for (int j = 0; j < result.size(); j++) {
            fout << result[j] << endl;
        }
    }

    fin.close();
    fout.close();

    return 0;
}

Trong đoạn code trên, chúng ta đọc dữ liệu từ tệp input.txt và ghi kết quả vào tệp output.txt. Để tạo hoán vị, chúng ta sử dụng hàm generate_permutations với các tham số tương tự như trong phiên bản Python.

Cuối cùng, chúng ta sử dụng hàm sort để sắp xếp kết quả theo thứ tự tăng dần của bảng chữ cái và ghi kết quả vào tệp output.txt.