Đếm cách chọn và trả lời nhanh nhiều câu hỏi tổ hợp

Lan có 5 tấm thẻ khác nhau và cần chọn 2 thẻ làm quà. Thứ tự đưa thẻ không quan trọng: chọn thẻ A rồi B vẫn là cùng một nhóm với B rồi A. Sau đó cô giáo hỏi thêm nhiều nhóm có kích thước khác nhau. Lan cần một cách đếm chính xác mà không phải liệt kê từng nhóm.

Thứ tự quyết định bạn đang đếm gì

Giả sử có ba thẻ A, B, C. Nếu hai vị trí là trưởng nhóm và thư ký, chọn A rồi B khác với chọn B rồi A. Nếu chỉ chọn một nhóm hai người, hai cách đó là một. Trước khi tính, bạn hãy xác định rõ mỗi kết quả được phân biệt bởi điều gì.

Đoạn chương trình sau liệt kê các nhóm và các cặp có thứ tự từ cùng ba thẻ:

from itertools import combinations, permutations
cards = ['A', 'B', 'C']
print(list(combinations(cards, 2)))
print(list(permutations(cards, 2)))

[('A', 'B'), ('A', 'C'), ('B', 'C')]
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

Mỗi nhóm hai thẻ tương ứng hai cặp có thứ tự. Với ba thẻ được chọn, mỗi nhóm tương ứng sáu cách xếp thứ tự. Khi các đối tượng khác nhau, số cách xếp k đối tượng là k!.

Giai thừa đếm cách xếp các đối tượng khác nhau

Giai thừa (factorial) n! là tích các số nguyên từ 1 đến n. Quy ước 0! = 1 vì có đúng một cách xếp không có đối tượng nào: cách xếp rỗng.

def factorial(n):
    answer = 1
    for value in range(1, n + 1):
        answer *= value
    return answer

for n in range(6):
    print(n, factorial(n))

0 1
1 1
2 2
3 6
4 24
5 120

Với n thẻ khác nhau, vị trí đầu có n lựa chọn, vị trí tiếp theo còn n - 1 lựa chọn. Tiếp tục nhân các số lựa chọn cho ta n!. Đoạn code trên thực hiện n phép nhân, tức O(n) phép nhân số nguyên. Khi số nguyên lớn dần, chi phí thực tế của từng phép nhân cũng tăng.

Tổ hợp đếm nhóm mà không xét thứ tự

Tổ hợp (combination) C(n, k) là số cách chọn k đối tượng từ n đối tượng khác nhau, không xét thứ tự. Với 0 <= k <= n, công thức là C(n, k) = n! / (k! * (n-k)!).

Để hiểu phép chia, trước hết chọn và xếp k đối tượng: có n! / (n-k)! cách. Nhưng mỗi nhóm được đếm k! lần, một lần cho mỗi thứ tự của cùng nhóm. Chia cho k! đưa số lần đếm của mỗi nhóm về một.

Với k = 3, mỗi nhóm được đếm 3! = 6 lần. Hàng sau biểu diễn sáu thứ tự của cùng một nhóm ba bạn; tất cả các ô tương ứng với đúng một nhóm.

Với 5 thẻ, C(5, 2) = 10. Bạn có thể dùng math.comb để tính chính xác khi không cần tự cài đặt:

from math import comb
for k in range(6):
    print(k, comb(5, k))

0 1
1 5
2 10
3 10
4 5
5 1

Chọn không thẻ hoặc chọn tất cả đều có một cách. Mỗi nhóm được chọn cũng xác định duy nhất nhóm bị bỏ lại. Vì thế C(n, k) = C(n, n-k).

from math import comb
print(comb(5, 2))
print(comb(5, 3))
print(comb(0, 0))

10
10
1

Có thể tính trực tiếp bằng tích, không cần tạo toàn bộ giai thừa. Tính đối xứng giúp số vòng lặp không lớn hơn nửa n. Sau vòng thứ i, kết quả là C(n, i) vì C(n, i) = C(n, i-1) * (n-i+1) / i. Tích C(n, i-1) * (n-i+1) bằng i * C(n, i) nên luôn chia hết cho i, và phép chia nguyên là chính xác.

n, k = 8, 3
k = min(k, n - k)
answer = 1
for i in range(1, k + 1):
    answer = answer * (n - i + 1) // i
    print(i, answer)

1 8
2 28
3 56

Ban đầu answer = 1 tương ứng với C(n, 0). Mỗi bước dùng quan hệ giữa hai hệ số tổ hợp liên tiếp. Thuật toán thực hiện O(min(k, n-k)) vòng nhân chia số nguyên. Chi phí từng phép toán còn phụ thuộc số chữ số của các số.

Tam giác Pascal xây mỗi kết quả từ hai kết quả nhỏ hơn

Xét một thẻ đặc biệt trong n thẻ. Một nhóm k thẻ hoặc không chứa thẻ đó, hoặc chứa thẻ đó. Hai trường hợp không trùng nhau, nên C(n, k) = C(n-1, k) + C(n-1, k-1).

Nếu không chọn thẻ đặc biệt, ta chọn k thẻ từ n-1 thẻ còn lại. Nếu đã chọn nó, ta chỉ cần chọn thêm k-1 thẻ. Ở hai biên, C(n, 0) = C(n, n) = 1.

Cách dựng mọi hàng đến n tính khoảng n(n+1)/2 ô. Với n = 1000, đó là khoảng nửa triệu ô, tức O(n²) phép cộng. Nếu chỉ giữ hàng hiện tại, bộ nhớ còn O(n). Quy tắc cộng vẫn dùng được với modulo bất kỳ.

Khi chỉ cần một hệ số, ta có thể lưu một hàng thay vì cả tam giác. Trước khi xử lý i, row[j] chứa hệ số hàng i-1. Cập nhật từ chỉ số lớn xuống nhỏ giữ row[j-1] thuộc hàng cũ. Đó là giá trị cần cộng theo quy tắc Pascal.

Chương trình sau nhận n, k và modulo m. Modulo 8 không nguyên tố, nhưng quy tắc Pascal vẫn hợp lệ vì không chia. Đầu vào trong hình cho phép bạn thử lại với giá trị khác.

6 3 8

n, k, m = map(int, input().split())
row = [0] * (k + 1)
row[0] = 1
for i in range(1, n + 1):
    for j in range(min(i, k), 0, -1):
        row[j] = (row[j] + row[j-1]) % m
print(row[k])

4

Kết quả là phần dư của C(6, 3). Duyệt tăng sẽ cộng nhầm một ô vừa thuộc hàng mới. Với n = 500 và k = 250, có không quá 125000 phép cập nhật. Bộ nhớ là O(k); thời gian là O(nk).

Chia thông thường không phải chia modulo

Với p = 7, số 3 có nghịch đảo modulo (modular inverse) là 5 vì 3 * 5 % 7 = 1. Thay vì chia cho 3 sau khi lấy dư, ta nhân với 5 rồi lấy dư.

p = 7
inverse = pow(3, p - 2, p)
print(inverse)
print(3 * inverse % p)

5
1

Theo định lý Fermat nhỏ, khi p nguyên tố và a không chia hết cho p, a^(p-2) là nghịch đảo của a modulo p. Xem Bài 7 để ôn lũy thừa nhanh. Nếu a chia hết cho p, không tồn tại nghịch đảo của nó modulo p.

for x in range(7):
    candidates = [y for y in range(7) if x * y % 7 == 1]
    print(x, candidates)

0 []
1 [1]
2 [4]
3 [5]
4 [2]
5 [3]
6 [6]

Trong modulo không nguyên tố, một số khác 0 cũng có thể không có nghịch đảo. Chẳng hạn 2 không có nghịch đảo modulo 8. Phép chia nguyên // sau khi lấy dư không khôi phục được thương ban đầu.

Tiền tính để trả lời nhiều truy vấn modulo

Giả sử p nguyên tố và mọi truy vấn đều có 0 <= k <= n <= N < p. Ta lưu fact[i] = i! % p và invfact[i] là nghịch đảo của fact[i]. Điều kiện N < p đảm bảo các giai thừa được lưu đều khác 0 modulo p.

Ví dụ này dùng p = 7 và tính đến chỉ số 4. Mỗi tích ở cột cuối có phần dư bằng 1. Đó chính là điều kiện để hai ô ở giữa là nghịch đảo của nhau.

Đối với C(4, 2), ta tra ba ô fact[4], invfact[2] và invfact[2]. Hai vị trí mẫu trùng nhau vẫn phải nhân hai lần. Mẫu số ban đầu cũng gồm hai thừa số giai thừa.

Đầu tiên tính fact theo chiều tăng. Sau đó tính một nghịch đảo bằng pow(fact[N], p-2, p). Từ fact[i] = fact[i-1] * i, suy ra invfact[i-1] = invfact[i] * i % p.

P = 1_000_000_007
queries = [(5, 2), (8, 3), (5, 0), (5, 5)]
limit = max(n for n, k in queries)
fact = [1] * (limit + 1)
for i in range(1, limit + 1):
    fact[i] = fact[i - 1] * i % P
invfact = [1] * (limit + 1)
invfact[limit] = pow(fact[limit], P - 2, P)
for i in range(limit, 0, -1):
    invfact[i - 1] = invfact[i] * i % P
for n, k in queries:
    print(fact[n] * invfact[k] * invfact[n - k] % P)

10
56
1
1

Mỗi kết quả đúng vì nhân fact[n] với nghịch đảo của hai giai thừa ở mẫu. Vòng lặp ngược đúng vì nhân nghịch đảo của i! với i cho nghịch đảo của (i-1)!. Phần tiền tính tốn O(N + log p) phép toán modulo và O(N) bộ nhớ. Mỗi truy vấn cần O(1) phép nhân modulo.

Với N = 100000 và q = 100000, hai vòng tiền tính thực hiện khoảng 200000 bước. Sau đó mỗi câu hỏi chỉ dùng một số cố định phép nhân. Nếu tính lại giai thừa từ đầu cho mỗi truy vấn, số bước có thể lên tới khoảng 10 tỷ.

Nếu n >= p, n! % p bằng 0 và không thể lấy nghịch đảo theo cách này. Cũng không được áp dụng công thức Fermat cho một modulo tùy ý. Những trường hợp đó cần phương pháp khác hoặc quy tắc Pascal khi kích thước đủ nhỏ.

Để đối chiếu, chương trình tiền tính có thể được kiểm tra với kết quả chính xác từ math.comb. Ở ví dụ sau, từng cặp (n, k) đều thỏa 0 <= k <= n < p.

from math import comb
p = 11
fact = [1] * p
for i in range(1, p):
    fact[i] = fact[i - 1] * i % p
invfact = [1] * p
invfact[-1] = pow(fact[-1], p - 2, p)
for i in range(p - 1, 0, -1):
    invfact[i - 1] = invfact[i] * i % p
print(all(fact[n] * invfact[k] * invfact[n-k] % p == comb(n, k) % p
          for n in range(p) for k in range(n + 1)))

True

Chọn thuật toán theo giới hạn và loại modulo

Không có một cách tính phù hợp mọi đề. Hãy xem số câu hỏi, cỡ n và điều kiện của modulo. Bảng sau giúp chọn hướng trước khi viết code.

Giả sử n <= 100000 và có 5000 truy vấn. Làm lại đến n mỗi lần có thể cần 500 triệu bước. Hai bảng tiền tính cần khoảng 200000 bước, rồi mỗi truy vấn chỉ dùng số phép nhân cố định. Đây là ước lượng phép tính, không phải cam kết thời gian trên mọi máy.

Ghép hai chặng đường bằng quy tắc nhân

Một robot đi trên lưới chỉ sang phải hoặc lên trên. Từ nhà đến điểm hẹn, robot cần 2 bước phải và 1 bước lên. Từ điểm hẹn đến thư viện, robot cần 1 bước phải và 1 bước lên. Một đường đi được xác định bởi vị trí của các bước phải.

Chặng đầu có C(3, 2) đường; chặng sau có C(2, 1) đường. Mỗi đường chặng đầu có thể ghép với mọi đường chặng sau. Hai đường hoàn chỉnh khác nhau nếu ít nhất một chặng khác nhau. Do đó số đường là tích của hai tổ hợp.

Đoạn sau kiểm tra kết quả bằng số nguyên. Với nhiều truy vấn lớn, thay hai lời gọi comb bằng tra bảng tiền tính.

from math import comb
a, b, c, d = 2, 1, 1, 1
first = comb(a + b, a)
second = comb(c + d, c)
print(first, second, first * second)

3 2 6

Nếu một chặng không có bước nào, chặng đó vẫn có một đường rỗng. Nhân với 1 giữ nguyên số lựa chọn của chặng còn lại. Nếu chỉ đếm đường từ đầu đến đích, kết quả có thể lớn hơn. Những đường không qua điểm hẹn không thỏa yêu cầu.

Lỗi thường gặp

Tóm tắt

• Tổ hợp đếm nhóm không xét thứ tự; hoán vị phân biệt thứ tự.
• Quy tắc Pascal chia các nhóm thành hai trường hợp rời nhau.
• Với p nguyên tố và n < p, tiền tính giai thừa cùng nghịch đảo giúp trả lời mỗi truy vấn trong O(1) phép toán modulo.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về math.comb.
• Hệ số nhị thức và tính modulo.
• Tài liệu Python về pow.