Thuật toán tổ hợp

8.1 Định nghĩa thuật toán tổ hợp.

Thuật toán tổ hợp — là các thuật toán được thiết kế để giải quyết các vấn đề liên quan đến việc đếm, liệt kê và tạo ra các cấu trúc tổ hợp khác nhau. Các thuật toán này được sử dụng để làm việc với tập hợp, tập con, hoán vị, tổ hợp và các đối tượng tổ hợp khác.

Các loại vấn đề tổ hợp chính

• Hoán vị: Tất cả các tổ hợp có thể sắp xếp được của các phần tử trong tập hợp.
• Tổ hợp: Tất cả các tập con không có thứ tự có kích thước xác định.
• Bố trí: Tất cả các tập con có thể sắp xếp được có kích thước xác định.
• Phân chia: Tất cả các cách có thể để chia một tập hợp thành các tập con.
• Đối tượng tổ hợp: Các cấu trúc khác, chẳng hạn như đồ thị, ma trận, v.v.

Ưu điểm và nhược điểm của thuật toán tổ hợp

Ưu điểm:

• Liệt kê đầy đủ: Các thuật toán này có thể liệt kê tất cả các tổ hợp có thể, điều này rất hữu ích cho các bài toán tìm kiếm toàn diện.
• Linh hoạt: Chúng có thể được điều chỉnh để giải quyết nhiều loại bài toán liên quan đến tổ hợp.
• Trực quan: Nhiều thuật toán dễ hiểu và thực hiện nhờ cách tiếp cận đệ quy và kỹ thuật backtracking.

Nhược điểm:

• Vụ nổ tổ hợp: Khi kích thước đầu vào tăng lên, thời gian thực hiện và dung lượng bộ nhớ có thể tăng mạnh (ví dụ, O(n!)).
• Không tối ưu: Trong trường hợp số lượng tổ hợp lớn, các thuật toán này có thể không hiệu quả và cần cải thiện hoặc thay thế bằng các kỹ thuật tiên tiến hơn (chẳng hạn như sử dụng lập trình động hoặc thuật toán tham lam).

Độ phức tạp thời gian và không gian của thuật toán tổ hợp

Độ phức tạp thời gian:

• Hoán vị: O(n!), với n là số lượng phần tử trong tập hợp.
• Tổ hợp: O(C(n, k)), với C(n, k) là hệ số nhị thức, bằng n! / (k! * (n - k)!).
• Bố trí: O(A(n, k)), với A(n, k) là số lượng bố trí, bằng n! / (n - k)!.
• Tập con: O(2^n), vì mỗi trong số n phần tử có thể được bao gồm hoặc không được bao gồm trong tập con.

Độ phức tạp không gian:

Thông thường là O(n) để lưu trữ kết quả trung gian trong quá trình xây dựng đệ quy, nhưng bộ nhớ cuối cùng có thể cần thiết để lưu trữ tất cả các kết quả (ví dụ, O(n * n!) cho hoán vị).

Ví dụ về thuật toán tổ hợp

8.2 Sinh hoán vị.

Bài toán:

Tìm tất cả các hoán vị duy nhất của các phần tử trong một tập hợp đã cho.

Thuật toán:

Sử dụng đệ quy hoặc phương pháp lặp để tạo ra tất cả các tổ hợp có thứ tự của các phần tử.

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

print(permute([1, 2, 3]))

8.3 Sinh tổ hợp

Bài toán:

Tìm tất cả các tổ hợp có kích thước xác định từ một tập hợp.

Thuật toán:

Sử dụng đệ quy hoặc lặp để tạo ra tất cả các tập con có kích thước xác định.

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

print(combine(4, 2))
        

8.4 Sinh phân chia tập hợp

Bài toán:

Tìm tất cả các cách có thể để chia một tập hợp thành các tập con.

Thuật toán:

Sử dụng đệ quy để tạo ra tất cả các phân chia có thể của tập hợp.

import copy

def partition_set(s):
    result = []

    def backtrack(part, rest):
        if not rest:
            result.append(copy.deepcopy(part[:]))
            return
        for i in range(len(part)):
            part[i].append(rest[0])
            backtrack(part, rest[1:])
            part[i].pop()
        part.append([rest[0]])
        backtrack(part, rest[1:])
        part.pop()

    backtrack([], list(s))
    return result

print(partition_set({1, 2, 3}))
        
        

Sử dụng copy.deepcopy(part[:]) tạo bản sao sâu của danh sách part.. Điều này có nghĩa là tạo ra một danh sách mới, độc lập không liên quan đến part gốc. Do đó, mỗi phần tử trong result sẽ đại diện cho một phân chia duy nhất.