Thuật toán sinh trong C++

Thuật toán sinh (hay còn gọi là thuật toán next permutation) là một thuật toán để tạo ra các hoán vị (permutation) khác nhau từ một hoán vị đã cho. Thuật toán này được sử dụng rộng rãi trong các bài toán liên quan đến xếp hạng, tổ chức, sắp xếp và tìm kiếm.

Thuật toán sinh hoán vị làm việc như sau:

Bắt đầu từ hoán vị đầu tiên đã cho, ta đi từ cuối lên đầu của hoán vị, tìm phần tử đầu tiên mà có giá trị nhỏ hơn phần tử bên cạnh nó.
Nếu không tìm thấy phần tử như vậy, hoán vị hiện tại là hoán vị cuối cùng, kết thúc thuật toán.
Nếu tìm thấy phần tử như vậy, ta tìm phần tử lớn nhất trong tất cả các phần tử bên phải của phần tử đó mà vẫn nhỏ hơn phần tử đó. Đổi chỗ phần tử nhỏ hơn với phần tử lớn nhất tìm được.
Cuối cùng, đảo ngược các phần tử bên phải của phần tử đầu tiên đã tìm được ở bước 1.

Ví dụ: Cho hoán vị ban đầu [1, 2, 3, 4, 5], ta sẽ thực hiện các bước sau để sinh ra tất cả các hoán vị khác nhau:

Bước 1: Tìm phần tử đầu tiên có giá trị nhỏ hơn phần tử bên cạnh nó, ta thấy phần tử 4 thỏa mãn điều kiện này.

Bước 2: Tìm phần tử lớn nhất trong các phần tử bên phải của phần tử đó mà vẫn nhỏ hơn phần tử đó, ta thấy phần tử 5 là phần tử lớn nhất như vậy.

Bước 3: Đổi chỗ phần tử 4 với phần tử 5.

Bước 4: Đảo ngược các phần tử bên phải của phần tử đầu tiên đã tìm được ở bước 1, ta được hoán vị kế tiếp là [1, 2, 3, 5, 4].

Tiếp tục thực hiện các bước trên cho đến khi không tìm thấy phần tử nào thỏa mãn điều kiện ở bước 1. Khi đó, ta đã sinh ra được tất cả các hoán vị khác nhau của hoán vị ban đầu.

Dưới đây là một đoạn code mẫu trong ngôn ngữ C++ để thực hiện thuật toán sinh hoán vị:

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void nextPermutation(vector<int>& nums) {
    int n = nums.size(), k, l;
    for (k = n - 2; k >= 0; k--) {
        if (nums[k] < nums[k + 1]) {
            break;
        }
    }
    if (k < 0) {
        reverse(nums.begin(), nums.end());
    } else {
        for (l = n - 1; l > k; l--) {
            if (nums[l] > nums[k]) {
                break;
            }
        }
        swap(nums[k], nums[l]);
        reverse(nums.begin() + k + 1, nums.end());
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    do {
        for (int num : nums) {
            cout << num << " ";
        }
        cout << endl;
        nextPermutation(nums);
    } while (nums[0] != 3 || nums[1] != 2 || nums[2] != 1);
    return 0;
}

Trong đoạn code trên, chúng ta sử dụng một vector để lưu trữ hoán vị ban đầu và sử dụng hàm nextPermutation để tạo ra các hoán vị khác nhau. Hàm nextPermutation sẽ trả về hoán vị kế tiếp của hoán vị đầu vào.

Trong hàm nextPermutation, chúng ta tìm kiếm phần tử đầu tiên từ cuối lên đầu mà có giá trị nhỏ hơn phần tử bên phải của nó (bước 1), sau đó tìm phần tử lớn nhất trong các phần tử bên phải của phần tử đó mà vẫn nhỏ hơn phần tử đó (bước 2) và đổi chỗ hai phần tử đó (bước 3). Cuối cùng, đảo ngược các phần tử bên phải của phần tử đầu tiên đã tìm được ở bước 1 (bước 4).

Trong hàm main, chúng ta sử dụng vòng lặp do-while để tạo ra tất cả các hoán vị khác nhau của hoán vị ban đầu và in chúng ra màn hình.

Lập trình C/C++

Thuật toán sinh trong C++

Trả lời Hủy