Chọn tổ hợp bằng quay lui

Lan có bốn thẻ đánh số từ 1 đến 4 và muốn chọn hai thẻ cho trò chơi. Nhóm gồm thẻ 1 và 3 chỉ được tính một lần, dù chọn thẻ nào trước. Lan cần liệt kê đủ sáu nhóm mà không lặp.

Mỗi lời gọi giữ một lựa chọn đang xây

Quay lui (backtracking) tổ chức việc thử các lựa chọn bằng đệ quy. Mỗi lời gọi giữ một trạng thái (state) mô tả phần nghiệm đã chọn và các khả năng còn lại. Nếu trạng thái đã hoàn chỉnh, ta ghi nhận nghiệm. Nếu chưa, ta thử một lựa chọn, đi sâu, rồi hoàn tác để thử lựa chọn khác.

path là danh sách lựa chọn trên nhánh hiện tại. append thay đổi danh sách đó; pop bỏ lựa chọn cuối sau khi lời gọi con kết thúc. Mỗi lời gọi trả về với path giống lúc nó được gọi.

Chương trình sau chọn một trong hai màu, sau đó chọn một trong hai hình. Bốn kết quả tương ứng bốn đường từ gốc tới lá.

choices = [("đỏ", "xanh"), ("tròn", "vuông")]
path = []
def visit(depth):
    if depth == len(choices):
        print(*path)
        return
    for item in choices[depth]:
        path.append(item)
        visit(depth + 1)
        path.pop()
visit(0)

đỏ tròn
đỏ vuông
xanh tròn
xanh vuông

Mỗi mức tương ứng một quyết định, nên một đường đi xác định đúng một cặp màu và hình. Vòng lặp thử cả hai khả năng ở mỗi mức nên không bỏ cặp nào. Với d mức và hai lựa chọn mỗi mức, cây đầy đủ có 2^d lá.

Khi trở về từ nhánh đỏ, tròn, pop bỏ tròn và giữ đỏ. Nhánh tiếp theo mới thêm vuông. Khi kết thúc cả hai hình, lệnh pop của mức màu bỏ tiếp đỏ. Mỗi lệnh hoàn tác thuộc về đúng lời gọi đã thêm phần tử tương ứng.

Lưu bản sao để các nghiệm không dùng chung danh sách

Nếu cần lưu các nghiệm thay vì in ngay, hãy chép path tại điểm dừng. answers.append(path) chỉ lưu tham chiếu tới cùng một danh sách đang tiếp tục thay đổi. Chương trình dưới đây so sánh hai cách lưu.

path = [1]
same = []
copies = []
same.append(path)
copies.append(path[:])
path.append(4)
print(same)
print(copies)

[[1, 4]]
[[1]]

same nhìn thấy thay đổi vì phần tử của nó là chính path. copies giữ bản sao độc lập tại thời điểm lưu. Với các phần tử là số nguyên, path[:] đủ để lưu một nghiệm. Nếu từng phần tử lại là đối tượng có thể thay đổi, bản sao nông chưa đủ bảo vệ các đối tượng bên trong.

Chỉ chọn số lớn hơn số vừa chọn để tránh trùng

Tổ hợp (combination) quan tâm tới các phần tử được chọn, không quan tâm thứ tự chọn. Trong bài của Lan, nhóm {1, 3} và {3, 1} là một nhóm. Mỗi nhóm có đúng một cách viết theo thứ tự tăng dần.

Ta gọi visit(start) khi các số đã chọn nằm trong path, còn số tiếp theo phải từ start đến n. Sau khi chọn x, lời gọi con dùng x + 1. Khi len(path) == k, ta in nghiệm và dừng nhánh đó.

n, k = 4, 2
path = []
def visit(start):
    if len(path) == k:
        print(*path)
        return
    for x in range(start, n + 1):
        path.append(x)
        visit(x + 1)
        path.pop()
visit(1)

1 2
1 3
1 4
2 3
2 4
3 4

Mỗi kết quả tăng nghiêm ngặt vì sau x chỉ xét số lớn hơn. Vì thế không có hai đường đi cùng biểu diễn một nhóm. Ngược lại, với bất kỳ nhóm k số khác nhau, chọn lần lượt theo thứ tự tăng dẫn tới đúng nhóm đó. Vòng lặp xét mọi giá trị cần thiết, nên không bỏ sót.

Với n = 4, k = 2, cây có sáu lá hợp lệ. Không phải mọi nút đều là nghiệm: nhánh bắt đầu bằng 4 không còn số lớn hơn để hoàn thành. Với k = 0, lời gọi ban đầu ghi nhận một tổ hợp rỗng. Với k > n, không có đường đi nào đủ dài.

Số nghiệm là C(n, k). Cách duyệt trên thăm tối đa 2^n trạng thái và in k số cho mỗi nghiệm. Một cận đơn giản là O(n * 2^n) thời gian và O(n) bộ nhớ trên ngăn xếp cùng path, chưa tính kết quả lưu lại. Ví dụ n = 16 có tối đa 65 536 tập lựa chọn; n = 40 đã vượt một nghìn tỉ.

Cắt nhánh khi không còn đủ số để chọn

Cắt nhánh (pruning) là dừng thử một phần cây sau khi chứng minh phần đó không thể tạo nghiệm cần tìm. Ở một trạng thái tổ hợp, đặt need = k - len(path). Nếu chọn x tiếp theo thì phải còn ít nhất need - 1 số sau x.

Do có n - x số lớn hơn x, điều kiện cần là n - x >= need - 1. Suy ra x <= n - need + 1. Đầu phải của range không được lấy, nên vòng lặp kết thúc ở n - need + 2.

Trong hình, con trỏ chỉ ô có giá trị 3; các ô bắt đầu đánh số từ 0. Giá trị 5 không thể đứng tiếp theo khi cần thêm hai số, vì sau nó không còn số nào. Ta không loại 5 khỏi mọi nghiệm: nó vẫn có thể được chọn sau 3 hoặc 4.

n, k = 5, 3
path = []
def visit(start):
    if len(path) == k:
        print(*path)
        return
    need = k - len(path)
    for x in range(start, n - need + 2):
        path.append(x)
        visit(x + 1)
        path.pop()
visit(1)

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Mọi nghiệm cần need - 1 số sau số tiếp theo, nên không nghiệm nào bắt đầu bằng giá trị bị bỏ. Các giá trị còn lại vẫn được thử. Vì vậy cắt nhánh này giữ nguyên tập nghiệm. Nó giảm các nhánh cụt nhưng vẫn phải in C(n, k) nghiệm; không thể kỳ vọng thời gian nhỏ hơn kích thước đầu ra.

Đếm nghiệm bằng hai quyết định tại mỗi vị trí

Khi chỉ cần số cách, không nhất thiết phải lưu mọi nghiệm. Ta xét lần lượt từng vị trí và cộng số nghiệm ở nhánh bỏ qua với số nghiệm ở nhánh chọn. Cách biểu diễn tập con đã có ở Bài 3 và Bài 21; ở đây ta tập trung vào đếm và điều kiện cắt nhánh.

Với các thẻ [2, 3, 5, 7], hãy đếm cách chọn các vị trí có tổng bằng 10. Hai thẻ có cùng giá trị ở hai vị trí khác nhau vẫn là hai lựa chọn khác nhau.

a = [2, 3, 5, 7]
target = 10
def count(i, total):
    if i == len(a):
        return int(total == target)
    return count(i + 1, total) + count(i + 1, total + a[i])
print(count(0, 0))

2

Mỗi tập vị trí quyết định duy nhất ở từng bước: chọn hoặc bỏ. Mỗi lá kiểm tra tổng một lần, nên tổng hai nhánh chính là số nghiệm. Dãy trên có hai cách: chọn 3 và 7, hoặc chọn 2, 3 và 5. Khi mục tiêu bằng 0, nhánh không chọn gì cũng được tính.

Cây nhị phân có 2^n lá và ít hơn 2^(n+1) nút. Do đó thời gian là O(2^n), bộ nhớ ngăn xếp là O(n). Với n = 20, khoảng một triệu lá có thể cần xét. Với n = 40, khoảng một nghìn tỉ lá khiến cách này không phù hợp nếu không có cấu trúc bổ sung.

Tổng hiện tại vượt đích chỉ an toàn để cắt khi không có số âm

Giả sử các số còn lại đều không âm. Nếu total > target, những lựa chọn tiếp theo không thể giảm tổng. Khi đó trả về 0 là an toàn. Tuy nhiên, gặp số âm về sau thì một tổng đang vượt đích vẫn có thể trở lại đích.

a = [8, -3]
target = 5
def count(i, total):
    if i == len(a):
        return int(total == target)
    return count(i + 1, total) + count(i + 1, total + a[i])
print(count(0, 0))

1

Nhánh chọn 8 có tổng lớn hơn 5, nhưng chọn tiếp -3 tạo tổng 5. Nếu cắt ngay tại 8, chương trình mất nghiệm. Trước khi áp dụng bất kỳ điều kiện cắt nào, hãy xét cả các giá trị biên và chứng minh mọi cách hoàn thành đều thất bại.

Với dữ liệu không âm, kiểm tra total > target cũng phải đặt đúng. Nếu total == target nhưng còn các số 0, vẫn có thể chọn hoặc bỏ từng số 0 để tạo các tập vị trí khác nhau. Vì thế không được trả về 1 ngay khi tổng vừa bằng đích.

a = [2, 0, 0]
def count(i, total):
    if total > 2:
        return 0
    if i == len(a):
        return int(total == 2)
    return count(i + 1, total) + count(i + 1, total + a[i])
print(count(0, 0))

4

Mỗi tiền tố ngoặc đúng giữ số đóng không vượt số mở

Một chuỗi ngoặc tròn đúng có số dấu mở bằng số dấu đóng. Ngoài ra, ở mọi tiền tố (prefix), số dấu đóng không được vượt số dấu mở. Chẳng hạn )( có cùng số dấu mở và đóng nhưng sai ngay tại ký tự đầu.

Ta xây chuỗi với opened dấu mở, closed dấu đóng và tối đa n cặp. Có thể thêm ( nếu opened < n. Có thể thêm ) nếu closed < opened. Khi cả hai bằng n, chuỗi hoàn chỉnh.

n = 3
path = []
def visit(opened, closed):
    if opened == n and closed == n:
        print(''.join(path))
        return
    if opened < n:
        path.append('(')
        visit(opened + 1, closed)
        path.pop()
    if closed < opened:
        path.append(')')
        visit(opened, closed + 1)
        path.pop()
visit(0, 0)

((()))
(()())
(())()
()(())
()()()

Điều kiện thêm dấu đóng giữ mọi tiền tố hợp lệ. Điểm dừng đảm bảo đủ n dấu mỗi loại. Ngược lại, mỗi chuỗi đúng chỉ dùng những bước được phép và có đúng một đường xây từng ký tự, nên được sinh đúng một lần.

Chiều sâu là 2n. Cây có không quá 2^(2n) lá và số nút cùng bậc. Khi tính cả việc tạo chuỗi, một cận an toàn là O(n * 4^n) thời gian. Bộ nhớ là O(n) nếu in ngay. Với n = 3, chỉ có năm chuỗi đúng. Với n = 10, vẫn cần cân nhắc thời gian và kích thước đầu ra trước khi liệt kê.

Để chỉ đếm, hàm có thể trả về tổng kết quả hai nhánh thay vì duy trì path. Trạng thái vẫn phải theo dõi cả hai số đếm.

def count(opened, closed, n):
    if opened == n and closed == n:
        return 1
    result = 0
    if opened < n:
        result += count(opened + 1, closed, n)
    if closed < opened:
        result += count(opened, closed + 1, n)
    return result
print(count(0, 0, 4))

14

Trường hợp n = 0 có một chuỗi rỗng. Điểm dừng kiểm tra ngay trạng thái ban đầu, nên hàm đếm đúng trường hợp này.

Dữ liệu vào quyết định kích thước cây cần duyệt

Khi đề cho n và k, chương trình cần đọc đúng hai số thay vì gắn sẵn ví dụ. Sau đây là chương trình đếm tổ hợp với cùng nguyên tắc số tăng dần. Nó không in từng tổ hợp nên chỉ in một số.

5 3

n, k = map(int, input().split())
def count(start, need):
    if need == 0:
        return 1
    result = 0
    for x in range(start, n - need + 2):
        result += count(x + 1, need - 1)
    return result
print(count(1, k))

10

Nếu k > n, vòng lặp rỗng và kết quả là 0. Nếu k = 0, kết quả là 1 cho tổ hợp rỗng. Với n = 5, k = 3, hàm xét mười nghiệm. Cận thời gian O(2^n) là đủ để lập kế hoạch ở giới hạn nhỏ, nhưng không chứng minh được chương trình phù hợp với n hàng trăm.

Lỗi thường gặp

Tóm tắt

• Một lời gọi mô tả trạng thái; chọn, đi sâu và hoàn tác giúp các nhánh độc lập.
• Tổ hợp tăng dần không trùng; start điều khiển các số có thể chọn tiếp.
• Chỉ cắt nhánh khi chứng minh không có nghiệm ở nhánh đó.
• Đếm nghiệm bằng tổng số nghiệm của các nhánh, kể cả nghiệm rỗng nếu đề cho phép.
• Với ngoặc đúng, mỗi tiền tố có ít nhất nhiều dấu mở bằng dấu đóng.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về cấu trúc dữ liệu và danh sách.
• Tài liệu Python về hàm và lời gọi hàm.