Thuật toán sinh với Python

NỘI DUNG

Giới thiệu về Thuật toán sinh

Thuật toán sinh là một phương pháp tạo ra tất cả các đối tượng của một tập hợp con hoặc tập hợp con của các đối tượng của một tập hợp. Nói cách khác, thuật toán sinh là một phương pháp để tạo ra tất cả các giá trị của một biến trong một tập giá trị đã cho mà không cần liệt kê tất cả các giá trị đó.

Một số bài toán cơ bản của thuật toán sinh bao gồm:

Liệt kê tất cả các hoán vị của một tập hợp: Với một tập hợp các phần tử đã cho, thuật toán sinh có thể được sử dụng để liệt kê tất cả các hoán vị của tập hợp đó.
Liệt kê tất cả các tổ hợp của một tập hợp: Thuật toán sinh có thể được sử dụng để liệt kê tất cả các tổ hợp của một tập hợp đó, từ các tổ hợp rỗng đến tổ hợp chứa tất cả các phần tử của tập hợp.
Liệt kê tất cả các cách phân chia của một tập hợp: Thuật toán sinh có thể được sử dụng để liệt kê tất cả các cách phân chia của một tập hợp đó thành các tập hợp con.
Liệt kê tất cả các cách sắp xếp của một tập hợp: Thuật toán sinh có thể được sử dụng để liệt kê tất cả các cách sắp xếp của một tập hợp đó, từ các sắp xếp đơn giản đến các sắp xếp phức tạp hơn.
Liệt kê tất cả các cây khung của một đồ thị: Thuật toán sinh có thể được sử dụng để liệt kê tất cả các cây khung của một đồ thị đã cho.

Trên thực tế, thuật toán sinh có thể được sử dụng để giải quyết một loạt các bài toán tổ hợp và tối ưu hóa khác trong khoa học máy tính và các lĩnh vực liên quan.

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

Dưới đây là các bước thực hiện thuật toán sinh:

Xác định tập hợp ban đầu: Bước đầu tiên trong thuật toán sinh là xác định tập hợp ban đầu mà bạn muốn sinh các giá trị từ đó.
Xác định một thứ tự cho các phần tử trong tập hợp ban đầu: Để sinh ra các giá trị theo thứ tự, bạn cần xác định một thứ tự cho các phần tử trong tập hợp ban đầu.
Tạo ra một hàm sinh: Bạn cần tạo ra một hàm sinh để sinh ra các giá trị của tập hợp con từ tập hợp ban đầu.
Thực hiện các phép tính: Thực hiện các phép tính trên các phần tử của tập hợp con để sinh ra các giá trị mới.
Kiểm tra điều kiện dừng: Sau mỗi lần sinh ra một giá trị mới, kiểm tra xem giá trị đó có phù hợp với điều kiện dừng hay không.
Lặp lại quá trình sinh giá trị mới: Nếu giá trị mới phù hợp với điều kiện dừng, lặp lại quá trình sinh giá trị mới cho đến khi tất cả các giá trị của tập hợp con đã được sinh ra.

Các bước trên có thể được thực hiện lại cho đến khi tất cả các giá trị của tập hợp đã được sinh ra hoặc đạt được một số giới hạn nào đó về số lượng giá trị sinh ra. Cụ thể, phần tiếp theo ta sẽ đi sâu phân tích về các bước thực hiện thuật toán sinh hoán vị.

Các bước thực hiện Thuật toán sinh hoán vị

Dưới đây là các bước của thuật toán sinh hoán vị:

Sắp xếp các phần tử của tập hợp ban đầu theo thứ tự tăng dần.
Liệt kê hoán vị đầu tiên: hoán vị đầu tiên của tập hợp được xác định bằng cách sắp xếp các phần tử theo thứ tự tăng dần.
Tạo ra hoán vị tiếp theo: Để tạo ra hoán vị tiếp theo, tìm phần tử cuối cùng trong hoán vị hiện tại mà có giá trị nhỏ hơn phần tử đứng ngay sau nó.
Đảo ngược tất cả các phần tử lớn hơn phần tử đó: Sau đó, đảo ngược tất cả các phần tử trong hoán vị đó mà có giá trị lớn hơn phần tử đó.
Lặp lại quá trình sinh hoán vị: Tiếp tục lặp lại các bước 3 và 4 cho đến khi tất cả các hoán vị của tập hợp đã được sinh ra.
Kiểm tra điều kiện dừng: Quá trình sinh hoán vị sẽ dừng khi hoán vị cuối cùng đã được sinh ra.

Ví dụ về Thuật toán sinh hoán vị

Dưới đây là một ví dụ về thuật toán sinh hoán vị với n = 3:

Giả sử chúng ta có danh sách các số nguyên từ 1 đến 3, và chúng ta muốn sinh tất cả các hoán vị của danh sách này.

Bước 1: Khởi tạo danh sách ban đầu là [1, 2, 3].

Bước 2: Tìm vị trí của phần tử lớn nhất mà đứng trước một phần tử nhỏ hơn nó. Trong trường hợp này, vị trí đó là 2, vì số 2 đứng trước số 3.

Bước 3: Tìm phần tử nhỏ nhất trong danh sách các phần tử đứng sau vị trí đã tìm ở bước 2 mà lớn hơn phần tử ở vị trí đó. Trong trường hợp này, số 3 là số nhỏ nhất lớn hơn số 2.

Bước 4: Đổi chỗ số 2 và số 3.

Bước 5: Đảo ngược danh sách các phần tử đứng sau vị trí đã tìm ở bước 2. Trong trường hợp này, danh sách các phần tử đứng sau vị trí 2 là [3], nên kết quả sau khi đảo ngược là [3].

Vì vậy, hoán vị đầu tiên sẽ là [1, 3, 2].

Bước 6: Lặp lại từ bước 2 đến bước 5 cho đến khi không còn cặp phần tử nào trong danh sách ban đầu có phần tử đứng trước nhỏ hơn phần tử đứng sau.

Kết quả là danh sách tất cả các hoán vị của danh sách ban đầu: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

Cài đặt Thuật toán sinh hoán vị với Python

def next_permutation(a):
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i >= 0:
        j = len(a) - 1
        while j >= 0 and a[i] >= a[j]:
            j -= 1
        a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])
    return a

# Sử dụng để kiểm tra hoạt động của hàm next_permutation
arr = [1, 2, 3]
while True:
    print(arr)
    arr = next_permutation(arr)
    if arr is None:
        break

Giải thích cho code trên:

Hàm next_permutation(a) nhận đầu vào là một list a, và trả về hoán vị tiếp theo của list a. Nếu không có hoán vị tiếp theo, hàm sẽ trả về None.
Biến i được sử dụng để tìm vị trí của phần tử đầu tiên từ phải sang trái mà có giá trị nhỏ hơn phần tử đứng ngay sau nó.
Nếu không tìm thấy phần tử như vậy, tức là list a đã là hoán vị cuối cùng, hàm trả về None.
Nếu tìm thấy phần tử như vậy, biến j được sử dụng để tìm phần tử lớn nhất từ phải sang trái mà lớn hơn phần tử ở vị trí i.
Sau khi tìm được vị trí i và j, phần tử tại vị trí i và j sẽ được hoán đổi.
Cuối cùng, các phần tử từ vị trí i+1 trở đi được đảo ngược.
Để kiểm tra hoạt động của hàm, chúng ta sử dụng một vòng lặp vô hạn để in ra tất cả các hoán vị của list [1, 2, 3]. Khi hàm next_permutation(a) trả về None, vòng lặp sẽ dừng lại.

Một số bài tập về thuật toán sinh hoán vị

Dưới đây là một số bài tập ứng dụng thuật toán sinh hoán vị:

Viết chương trình sinh ra tất cả các hoán vị của một tập hợp các số nguyên cho trước.
Tìm hoán vị kế tiếp của một hoán vị cụ thể.
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.
Viết chương trình tìm tất cả các hoán vị của một chuỗi ký tự.
Tìm tất cả các hoán vị của một tập hợp các chữ cái Latinh.
Tìm số lượng hoán vị của một tập hợp các phần tử cho trước.
Sử dụng thuật toán sinh hoán vị để giải quyết bài toán xếp hậu (n-queens problem).
Tìm hoán vị có tổng giá trị lớn nhất hoặc nhỏ nhất đối với một tập hợp các số nguyên cho trước.
Sắp xếp một mảng số nguyên bằng cách sử dụng thuật toán sinh hoán vị.
Tìm số lượng hoán vị của một tập hợp các phần tử mà không có hai phần tử nào nằm cạnh nhau (không có phần tử nào được lặp lại liên tiếp).

Cài đặt thuật toán sinh hoán vị với hàm có sẵn trong Python

Trong Python, chúng ta có thể sử dụng module itertools để sinh ra tất cả các hoán vị của một list. Cụ thể, chúng ta có thể sử dụng hàm permutations để sinh ra tất cả các hoán vị của một list.

Dưới đây là một ví dụ về cài đặt thuật toán sinh hoán vị bằng hàm permutations trong Python:

import itertools

# Hàm sinh tất cả các hoán vị của một list
def generate_permutations(arr):
    return itertools.permutations(arr)

# Sử dụng để kiểm tra hoạt động của hàm generate_permutations
arr = [1, 2, 3]
for permutation in generate_permutations(arr):
    print(permutation)

Giải thích cho code trên:

Hàm generate_permutations(arr) sử dụng hàm permutations trong module itertools để sinh ra tất cả các hoán vị của list arr.
Vòng lặp for được sử dụng để duyệt qua từng hoán vị được sinh ra bởi hàm generate_permutations(arr).
Mỗi hoán vị được in ra bởi lệnh print(permutation).
Với đầu vào là list [1, 2, 3], chương trình sẽ sinh ra và in ra tất cả 6 hoán vị của list đó, tức là: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Đánh giá độ phức tạp của thuật toán

Độ phức tạp của thuật toán sinh hoán vị là O(n*n!), trong đó n là số lượng phần tử trong danh sách ban đầu. Độ phức tạp này đến từ việc có n! hoán vị khác nhau của n phần tử, mỗi hoán vị lại cần O(n) để được sinh ra. Tổng quát hơn, độ phức tạp là O(n! * n).

Đối với thuật toán sinh hoán vị có sẵn trong Python (cụ thể là hàm permutations() trong thư viện itertools), độ phức tạp là O(n!), giống như thuật toán sinh hoán vị thông thường. Tuy nhiên, vì việc sử dụng các hàm có sẵn giúp chúng ta tối ưu hóa quá trình lập trình và giảm thiểu các lỗi cú pháp hay logic, nên chúng ta không cần phải tốn thời gian viết và kiểm tra thuật toán. Ngoài ra, hàm permutations() được tối ưu hóa để chạy nhanh hơn so với cách cài đặt thuật toán truyền thống.

Vì vậy, dù cho cả hai phương pháp đều có độ phức tạp tương đương nhau, sử dụng hàm có sẵn trong Python có thể giúp chúng ta tiết kiệm được thời gian và nâng cao tính ổn định của chương trình.

Liệt kê dãy nhị phân có độ dài n

Ở đây, ta sẽ sử dụng thuật toán sinh để liệt kê tất cả các dãy nhị phân có độ dài n bằng cách sinh ra tất cả các hoán vị của [0, 1] với độ dài n và sử dụng nó như một chỉ mục để lấy giá trị tại vị trí tương ứng. Ta sẽ sử dụng thư viện itertools của Python để thực hiện việc sinh hoán vị.

import itertools

def generate_binary_sequences(n):
    # Tạo một danh sách chứa các giá trị [0, 1] với độ dài n
    values = [0] * n + [1] * n
    # Lấy tất cả các hoán vị của danh sách trên
    permutations = itertools.permutations(values, n)
    # Duyệt qua từng hoán vị
    for permutation in permutations:
        # Tạo dãy nhị phân từ hoán vị tương ứng
        binary_sequence = [str(i) for i in permutation]
        yield "".join(binary_sequence)

Hàm generate_binary_sequences(n) trên sẽ tạo ra tất cả các dãy nhị phân có độ dài n. Ta sử dụng hàm itertools.permutations để sinh ra tất cả các hoán vị của danh sách [0, 1] với độ dài n, và duyệt qua từng hoán vị để tạo ra dãy nhị phân tương ứng.

Để sử dụng hàm trên, ta có thể gọi:

n = 3
for binary_sequence in generate_binary_sequences(n):
    print(binary_sequence)

Kết quả sẽ là:

Liệt kê dãy Tổ hợp chập k của n

Thuật toán sinh cũng có thể được sử dụng để liệt kê tất cả các tổ hợp chập k của n. Ta có thể sử dụng thuật toán sinh để tạo ra tất cả các chỉ số của các phần tử trong một tập hợp kích thước n, sau đó lọc ra các chỉ số tương ứng với các tổ hợp chập k.

def generate_combinations(n, k):
    # Tạo một danh sách chứa các chỉ số của các phần tử trong một tập hợp kích thước n
    indices = list(range(n))
    # Tạo tất cả các hoán vị của danh sách trên với độ dài k
    permutations = itertools.combinations(indices, k)
    # Duyệt qua từng hoán vị
    for permutation in permutations:
        # Trả về danh sách các phần tử tương ứng với chỉ số trong tổ hợp chập k
        yield [i+1 for i in permutation]

Hàm generate_combinations(n, k) trên sẽ tạo ra tất cả các tổ hợp chập k của tập hợp kích thước n. Ta sử dụng hàm itertools.combinations để sinh ra tất cả các tổ hợp chập k của danh sách các chỉ số của các phần tử trong tập hợp kích thước n, và duyệt qua từng tổ hợp chập k để tạo ra danh sách các phần tử tương ứng.