Tìm hoán vị đầu tiên và hoán vị cuối cùng

Bài toán

Tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp các phần tử được sắp xếp theo thứ tự từ điển.

Giới thiệu bài toán

Bài toán tìm hoán vị đầu tiên và cuối cùng của một tập hợp các phần tử được sắp xếp theo thứ tự từ điển là một bài toán thường được sử dụng trong lĩnh vực toán học, khoa học máy tính và các ứng dụng liên quan đến tìm kiếm và sắp xếp.

Trong bài toán này, ta được cung cấp một tập hợp các phần tử được sắp xếp theo thứ tự từ điển và cần tìm ra hoán vị đầu tiên và cuối cùng của tập hợp đó. Hoán vị đầu tiên của tập hợp là hoán vị được sắp xếp đầu tiên theo thứ tự từ điển, còn hoán vị cuối cùng của tập hợp là hoán vị được sắp xếp cuối cùng theo thứ tự từ điển.

Các bước thực hiện thuật toán

  1. Tìm hoán vị đầu tiên: Để tìm hoán vị đầu tiên, ta có thể sử dụng thuật toán “Next Permutation” (hoán vị tiếp theo). Ta bắt đầu từ hoán vị đầu tiên của tập hợp và tiếp tục áp dụng thuật toán “Next Permutation” cho đến khi không còn hoán vị tiếp theo. Khi đó, hoán vị hiện tại là hoán vị đầu tiên của tập hợp.

  2. Tìm hoán vị cuối cùng: Để tìm hoán vị cuối cùng, ta cũng bắt đầu từ hoán vị đầu tiên và tiếp tục áp dụng thuật toán “Next Permutation” cho đến khi không còn hoán vị tiếp theo. Khi đó, hoán vị hiện tại là hoán vị cuối cùng của tập hợp.

Ví dụ về thuật toán

Giả sử ta có tập hợp các phần tử sau đây: [1, 2, 3, 4]. Để tìm hoán vị đầu tiên, ta bắt đầu từ hoán vị đầu tiên của tập hợp: [1, 2, 3, 4] và tiếp tục áp dụng thuật toán “Next Permutation” cho đến khi không còn hoán vị tiếp theo. Kết quả sẽ là hoán vị đầu tiên của tập hợp: [1, 2, 3, 4].

Để tìm hoán vị cuối cùng của tập hợp này, ta cũng bắt đầu từ hoán vị đầu tiên [1, 2, 3, 4]và tiếp tục áp dụng thuật toán “Next Permutation” cho đến khi không còn hoán vị tiếp theo. Kết quả sẽ là hoán vị cuối cùng của tập hợp:[4, 3, 2, 1].

Cài đặt thuật toán

Để cài đặt thuật toán tìm hoán vị đầu tiên và cuối cùng của một tập hợp được sắp xếp theo thứ tự từ điển, ta có thể sử dụng hàm next_permutation trong các ngôn ngữ lập trình như C++, Python hoặc Java.

Ví dụ, trong C++, ta có thể sử dụng hàm next_permutation như sau:

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

using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4};

    // Tìm hoán vị đầu tiên
    sort(v.begin(), v.end());
    do {
        for (int x : v) {
            cout << x << " ";
        }
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));

    // Tìm hoán vị cuối cùng
    sort(v.begin(), v.end(), greater<int>());
    do {
        for (int x : v) {
            cout << x << " ";
        }
        cout << endl;
    } while (prev_permutation(v.begin(), v.end()));
    
    return 0;
}

Dưới đây là cài đặt bài toán tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp các phần tử được sắp xếp theo thứ tự từ điển bằng Python:

from itertools import permutations

# Hàm tìm hoán vị đầu tiên của tập hợp sắp xếp theo thứ tự từ điển
def first_permutation(lst):
    # Sắp xếp tập hợp
    lst.sort()
    # Tìm hoán vị đầu tiên
    for p in permutations(lst):
        return p

# Hàm tìm hoán vị cuối cùng của tập hợp sắp xếp theo thứ tự từ điển
def last_permutation(lst):
    # Sắp xếp tập hợp theo thứ tự ngược lại
    lst.sort(reverse=True)
    # Tìm hoán vị cuối cùng
    for p in permutations(lst):
        return p

# Sử dụng hàm để tìm hoán vị đầu tiên và cuối cùng của tập hợp
lst = [1, 2, 3]
print("First permutation:", first_permutation(lst))
print("Last permutation:", last_permutation(lst))

Trong đoạn code trên, chúng ta sử dụng module itertools của Python để lấy tất cả các hoán vị của tập hợp bằng hàm permutations(). Hàm first_permutation() sẽ trả về hoán vị đầu tiên của tập hợp đã cho, còn hàm last_permutation() sẽ trả về hoán vị cuối cùng của tập hợp đã cho.

Lưu ý rằng, trong trường hợp số lượng phần tử trong tập hợp lớn, việc tìm tất cả các hoán vị có thể trở nên khó khăn và tốn nhiều thời gian tính toán.

Đánh giá độ phức tạp

Độ phức tạp của thuật toán tìm hoán vị đầu tiên và cuối cùng của một tập hợp được sắp xếp theo thứ tự từ điển là O(n!), trong đó n là số phần tử của tập hợp. Điều này bởi vì trong trường hợp tốt nhất, ta phải tạo ra O(n!) hoán vị khác nhau của tập hợp để tìm được hoán vị đầu tiên và cuối cùng.

Thuật toán đảo ngược

Thuật toán tối ưu nhất cho bài toán tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp các phần tử được sắp xếp theo thứ tự từ điển là sử dụng phương pháp đảo ngược.

Giả sử chúng ta có một tập hợp các phần tử được sắp xếp theo thứ tự từ điển, và chúng ta muốn tìm hoán vị đầu tiên của tập hợp này. Để làm được điều này, chúng ta có thể thực hiện các bước sau đây:

  1. Kiểm tra xem tập hợp có ít nhất hai phần tử không giống nhau không. Nếu không, tập hợp đã cho là một hoán vị và không có hoán vị khác.

  2. Tìm phần tử cuối cùng của tập hợp có thể được đổi chỗ để tạo thành một hoán vị mới. Để làm được điều này, ta duyệt tập hợp từ cuối lên đầu cho đến khi gặp phần tử đầu tiên mà có thể được đổi chỗ với một phần tử có giá trị nhỏ hơn nó.

  3. Tìm phần tử nhỏ nhất trong các phần tử nằm sau phần tử được tìm thấy ở bước 2 và lớn hơn nó. Để làm được điều này, ta duyệt các phần tử từ phần tử được tìm thấy ở bước 2 đến phần tử cuối cùng của tập hợp.

  4. Đổi chỗ phần tử được tìm thấy ở bước 2 với phần tử được tìm thấy ở bước 3.

  5. Đảo ngược các phần tử nằm sau phần tử được tìm thấy ở bước 2.

  6. Hoán vị mới tạo thành chính là hoán vị kế tiếp theo của tập hợp đã cho.

Tương tự, để tìm hoán vị cuối cùng của tập hợp, chúng ta có thể sử dụng phương pháp đảo ngược kết hợp với phương pháp tìm hoán vị đầu tiên.

Với phương pháp này, ta chỉ cần duyệt qua tất cả các phần tử của tập hợp một lần duy nhất, do đó độ phức tạp của thuật toán là O(n), trong đó n là số lượng phần tử của tập hợp.

Cài đặt thuật toán đảo ngược

Dưới đây là mã Python cho phương pháp tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp được sắp xếp theo thứ tự từ điển bằng cách sử dụng phương pháp đảo ngược:

def next_permutation(arr):
    n = len(arr)
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i == -1:
        return None 

    j = n - 1
    while arr[i] >= arr[j]:
        j -= 1

    arr[i], arr[j] = arr[j], arr[i]
    arr[i+1:] = reversed(arr[i+1:])

    return arr

def prev_permutation(arr):
    n = len(arr)
    i = n - 2
    while i >= 0 and arr[i] <= arr[i + 1]:
        i -= 1
    if i == -1:
        return None  

    j = n - 1
    while arr[i] <= arr[j]:
        j -= 1

    arr[i], arr[j] = arr[j], arr[i]
    arr[i+1:] = reversed(arr[i+1:])

    return arr

Hàm next_permutation(arr) trả về hoán vị kế tiếp của tập hợp arr, hoặc None nếu arr đã là hoán vị cuối cùng. Tương tự, hàm prev_permutation(arr) trả về hoán vị trước đó của tập hợp arr, hoặc None nếu arr đã là hoán vị đầu tiên.

Dưới đây là cài đặt thuật toán đảo ngược để tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp được sắp xếp theo thứ tự từ điển bằng ngôn ngữ C++:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> next_permutation(vector<int> arr) {
    int n = arr.size();
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    if (i == -1) {
        return {}; // arr is the last permutation
    }

    int j = n - 1;
    while (arr[i] >= arr[j]) {
        j--;
    }

    swap(arr[i], arr[j]);
    reverse(arr.begin() + i + 1, arr.end());

    return arr;
}

vector<int> prev_permutation(vector<int> arr) {
    int n = arr.size();
    int i = n - 2;
    while (i >= 0 && arr[i] <= arr[i + 1]) {
        i--;
    }
    if (i == -1) {
        return {}; // arr is the first permutation
    }

    int j = n - 1;
    while (arr[i] <= arr[j]) {
        j--;
    }

    swap(arr[i], arr[j]);
    reverse(arr.begin() + i + 1, arr.end());

    return arr;
}

int main() {
    vector<int> arr = {1, 2, 3};

    // find the first permutation
    vector<int> first_permutation = arr;
    while (!first_permutation.empty()) {
        // print the current permutation
        for (int x : first_permutation) {
            cout << x << " ";
        }
        cout << endl;

        first_permutation = prev_permutation(first_permutation);
    }

    // find the last permutation
    vector<int> last_permutation = arr;
    while (!last_permutation.empty()) {
        // print the current permutation
        for (int x : last_permutation) {
            cout << x << " ";
        }
        cout << endl;

        last_permutation = next_permutation(last_permutation);
    }

    return 0;
}

Ở đây, chúng ta sử dụng hàm swap() để hoán đổi các phần tử của tập hợp, và hàm reverse() để đảo ngược thứ tự các phần tử của một đoạn trong tập hợp. Chúng ta cũng sử dụng vòng lặp while để tìm các hoán vị kế tiếp hoặc trước đó cho đến khi không còn hoán vị nào còn lại.

Kết luận

Độ phức tạp của thuật toán thông thường để tìm hoán vị đầu tiên và hoán vị cuối cùng của một tập hợp được sắp xếp theo thứ tự từ điển là O(n*n!), trong đó n là số phần tử của tập hợp. Thuật toán này sẽ liệt kê tất cả các hoán vị của tập hợp, sau đó so sánh với hoán vị ban đầu để tìm hoán vị đầu tiên và hoán vị cuối cùng.

So sánh với thuật toán đảo ngược, thuật toán thông thường có độ phức tạp lớn hơn đáng kể. Vì vậy, thuật toán đảo ngược là lựa chọn tốt hơn để giải quyết bài toán này, vì nó có độ phức tạp tối ưu là O(n), tốc độ thực thi nhanh hơn và tiết kiệm không gian bộ nhớ hơn./.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *