Đếm các đối tượng thỏa ít nhất một điều kiện

Lan phát quà cho 30 học viên có số vé chia hết cho 4 hoặc 6. Bạn Bình có vé 12 nên thuộc cả hai nhóm. Lan cần biết có bao nhiêu vé nhận quà, nhưng cộng hai danh sách sẽ tính vé của Bình hai lần.

Cộng hai nhóm rồi bỏ một lần đếm trùng

Gọi A là tập học viên đăng ký vẽ và B là tập đăng ký nhạc. Hợp (union) gồm những học viên thuộc ít nhất một nhóm. Giao (intersection) gồm những học viên thuộc cả hai nhóm.

Giả sử nhóm vẽ có An, Bình, Chi; nhóm nhạc có Bình, Chi, Dung. Nếu chỉ cộng hai kích thước, Bình và Chi đều xuất hiện hai lần. Ta cần bỏ một lượt xuất hiện của mỗi bạn trong giao.

a = {"An", "Bình", "Chi"}
b = {"Bình", "Chi", "Dung"}
print("Vẽ:", len(a), "Nhạc:", len(b))
print("Cả hai:", len(a & b))
print("Ít nhất một:", len(a) + len(b) - len(a & b))

Vẽ: 3 Nhạc: 3
Cả hai: 2
Ít nhất một: 4

Kết quả cuối là số học viên khác nhau. Mỗi bạn thuộc một nhóm được cộng một lần. Mỗi bạn thuộc hai nhóm được cộng hai lần rồi trừ một lần.

Quy tắc này gọi là bao hàm – loại trừ (inclusion–exclusion): |A ∪ B| = |A| + |B| - |A ∩ B|. Nếu hai nhóm không giao nhau, số bị trừ bằng không. Nếu hai nhóm trùng nhau, phép trừ giữ lại đúng một bản của cả nhóm.

Đừng nhầm “hoặc” trong bài đếm với “chỉ một trong hai”. Người thuộc cả hai vẫn được nhận quà khi đề nói “ít nhất một”. Đề “đúng một” phải bỏ cả hai lượt đóng góp của phần giao.

Trước khi viết công thức, hãy xác định đối tượng được đếm là gì. Nếu đề đếm học viên, mỗi học viên là một đối tượng dù đăng ký nhiều hoạt động. Nếu đề đếm lượt đăng ký, cùng một học viên có thể tạo hai lượt khác nhau. Với hai câu hỏi đó, bạn cần hai miền đối tượng khác nhau.

Định nghĩa nhóm cũng phải nhất quán với miền. Trong ví dụ vé, chỉ những số từ 1 đến 30 mới thuộc các nhóm được đếm. Một số chia hết cho 4 nhưng lớn hơn 30 không tạo thêm vé nhận quà. Quy tắc cộng trừ chỉ có ý nghĩa khi các nhóm cùng nằm trong miền xét.

Chương trình sau đối chiếu ba cách hỏi trên cùng dữ liệu. Phép ^ lấy phần tử thuộc đúng một trong hai tập:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print("Ít nhất một:", len(a | b))
print("Đúng một:", len(a ^ b))
print("Cả hai:", len(a & b))

Ít nhất một: 5
Đúng một: 3
Cả hai: 2

Các phần tử 3 và 4 thuộc giao. Chúng có mặt trong hợp nhưng không thuộc kết quả “đúng một”. Công thức cho đúng một là |A| + |B| - 2 * |A ∩ B|.

Giao của các bội được đếm bằng bội chung nhỏ nhất

Trong tình huống vé của Lan, A là các số từ 1 đến 30 chia hết cho 4. B là các số trong cùng miền chia hết cho 6. Những số thuộc giao phải chia hết cho cả 4 và 6.

Bội chung nhỏ nhất (least common multiple), viết là lcm, của 4 và 6 là 12. Mọi bội chung dương đều là bội của 12. Vì vậy có n // lcm(a, b) số thuộc giao trong đoạn từ 1 đến n.

Ô 12 thuộc cả hai nhóm, còn các ô 4, 6 và 8 chỉ thuộc một nhóm. Hình chỉ thể hiện 12 vé đầu; công thức phía dưới đếm đủ 30 vé.

Python có math.lcm. Bạn cũng có thể dùng a // gcd(a, b) * b với hai số nguyên dương. Phép chia trước nhân tạo số trung gian nhỏ hơn.

from math import gcd

n, a, b = 30, 4, 6
common = a // gcd(a, b) * b
print("Bội chung nhỏ nhất:", common)
print("Số vé:", n // a + n // b - n // common)

Bội chung nhỏ nhất: 12
Số vé: 10

Vé 12 và 24 được trừ một lượt vì từng được tính ở cả hai nhóm. Không thể dùng a * b thay cho lcm(a, b) khi hai số có ước chung lớn hơn 1. Chẳng hạn, tích 24 bỏ sót vé 12 trong giao.

Nếu a = b, hai nhóm trùng nhau và công thức vẫn đúng. Nếu a = 1, mọi vé trong miền đều thuộc nhóm đầu. Nếu lcm(a, b) > n, giao không có số dương nào trong miền.

Chia nguyên đếm được số bội vì các bội dương của a lần lượt là a, 2*a, 3*a và cứ thế tiếp tục. Số bội lớn nhất không vượt n ứng với hệ số n // a. Ta đang đếm từ 1; số 0 không nằm trong miền và không được cộng thêm.

Ví dụ, nếu n = 3 và cả hai chu kỳ đều lớn hơn 3, không có vé nào thỏa điều kiện. Công thức trả 0 vì cả hai số hạng đơn lẫn số hạng giao đều bằng 0. Không cần viết riêng một nhánh cho trường hợp đó.

Đoạn code sau đọc một truy vấn với n = 10, a = 7, b = 9. Cả hai nhóm đều có thành viên, nhưng giao nằm ngoài miền:

10 7 9

from math import lcm
n, a, b = map(int, input().split())
print(n // a + n // b - n // lcm(a, b))

2

Phép tính chỉ gọi gcd một lần và làm một số phép số học. Với các số dương không vượt 10^6, thuật toán Euclid cần O(log max(a, b)) bước chia. Bộ nhớ phụ là O(1) nếu coi kích thước các số là cố định.

Ba nhóm cần cộng lại giao của cả ba

Xét các vé từ 1 đến 30 chia hết cho 2, 3 hoặc 5. Gọi ba nhóm tương ứng là A, B, C. Tổng ba kích thước tính một vé thuộc cả ba nhóm tới ba lần.

Khi trừ ba giao đôi, vé thuộc cả ba lại bị trừ ba lần. Tổng đóng góp lúc này là 3 - 3 = 0, dù vé đó cần được đếm một lần. Ta cộng giao ba một lần để sửa điều này.

Với ba nhóm, quy tắc là cộng ba nhóm đơn, trừ ba giao đôi, rồi cộng giao ba. Bạn có thể kiểm tra đóng góp của từng loại vé bằng bảng được chương trình tạo:

Một vé ngoài mọi nhóm có đóng góp 0. Vé thuộc một, hai hoặc ba nhóm đều đóng góp 1. Điều này chứng minh công thức đếm đúng, kể cả khi các nhóm trùng nhau.

Bảng này xét một đối tượng bất kỳ, thay vì dựa vào hình dạng của ba nhóm. Điều đó quan trọng khi một nhóm nằm hoàn toàn trong nhóm khác. Dù giao đôi và giao ba có cùng phần tử, mỗi lần xuất hiện trong công thức vẫn có vai trò riêng. Không được gộp các số hạng chỉ vì chúng có cùng kích thước.

Chương trình dưới đây tính các giao bằng lcm:

from math import lcm
n = 30
a, b, c = 2, 3, 5
single = n // a + n // b + n // c
pair = n // lcm(a, b) + n // lcm(a, c) + n // lcm(b, c)
triple = n // lcm(a, b, c)
print("Nhóm đơn:", single)
print("Giao đôi:", pair)
print("Giao ba:", triple)
print("Ít nhất một:", single - pair + triple)

Nhóm đơn: 31
Giao đôi: 10
Giao ba: 1
Ít nhất một: 22

Mỗi nhóm đơn hoặc giao được tính một lần bằng phép chia nguyên. Có bảy tập con không rỗng của ba điều kiện. Số phép tính không phụ thuộc vào số vé; chi phí chủ yếu là tính lcm.

Quy tắc cũng áp dụng cho chuỗi, không chỉ phép chia

Một mã gồm ba ký tự, mỗi vị trí chọn A hoặc B. Người quản lý muốn đếm mã có ít nhất một ký tự A. Có tám mã vì mỗi vị trí có hai lựa chọn.

Gọi A1, A2, A3 là nhóm mã có chữ A ở vị trí tương ứng. Mỗi nhóm đơn cố định một vị trí nên có 2² mã. Mỗi giao đôi cố định hai vị trí nên có 2 mã; giao ba chỉ có AAA.

from itertools import product
words = ["".join(p) for p in product("AB", repeat=3)]
by_union = 3 * 2**2 - 3 * 2 + 1
by_listing = sum("A" in word for word in words)
print("Các mã:", *words)
print("Bao hàm – loại trừ:", by_union)
print("Đếm trực tiếp:", by_listing)

Các mã: AAA AAB ABA ABB BAA BAB BBA BBB
Bao hàm – loại trừ: 7
Đếm trực tiếp: 7

Hai cách cho cùng số lượng. Ở đây giao được tính bằng cách cố định vị trí, không dùng lcm. Trước khi áp dụng công thức, bạn phải tìm cách đếm từng giao theo ý nghĩa của dữ liệu.

Chẳng hạn giao của A1 và A3 gồm các mã bắt đầu và kết thúc bằng A. Vị trí giữa vẫn có hai lựa chọn độc lập. Một mã như AAA nằm trong cả ba giao đôi và cũng nằm trong giao ba. Vì vậy mã đó được sửa số lần đếm bằng đúng quy tắc ba nhóm.

Với ba vị trí, liệt kê tám mã là cách kiểm chứng thuận tiện. Khi có 40 vị trí, số mã là 2^40, nên liệt kê từng mã không còn thực tế. Nếu mỗi vị trí chỉ có hai lựa chọn, bài này còn có cách dùng phần bù nhanh hơn.

Phần bù biến câu hỏi không thỏa thành phép trừ

Phần bù (complement) của một nhóm gồm các đối tượng trong miền xét nhưng không thuộc nhóm đó. Nếu biết tổng số đối tượng và số thuộc ít nhất một điều kiện, ta lấy tổng trừ số đó.

Với mã ba ký tự ở trên, chỉ mã BBB không chứa A. Bạn có thể đếm phần bù rồi trừ khỏi tổng. Đối với nhiều vị trí, cách này tránh duyệt mọi tập con của vị trí.

length = 40
total = 2 ** length
without_a = 1
print("Tổng mã:", total)
print("Có ít nhất một A:", total - without_a)

Tổng mã: 1099511627776
Có ít nhất một A: 1099511627775

Tương tự, từ 1 đến n, số không chia hết cho a lẫn b bằng n trừ số chia hết cho ít nhất một trong hai. Miền ở đây có đúng n số vì bắt đầu từ 1. Nếu miền thay đổi, tổng phải thay đổi theo.

from math import lcm
n, a, b = 30, 4, 6
bad = n // a + n // b - n // lcm(a, b)
print("Không thuộc lịch nào:", n - bad)

Không thuộc lịch nào: 20

Điều kiện “không chia hết cho cả a lẫn b” ở đây có nghĩa không chia hết cho a và cũng không chia hết cho b. Điều kiện “không chia hết đồng thời cho cả hai” lại cho phép một số thuộc đúng một nhóm. Hai cách hiểu tạo ra các tập khác nhau.

Hiệu hai lần đếm lấy đúng đoạn đóng

Đặt F(x) là số nguyên từ 1 đến x chia hết cho a hoặc b. Với x = 0, miền rỗng nên F(0) = 0. Muốn đếm trong đoạn đóng từ L đến R, ta tính F(R) - F(L - 1).

Lý do là các số từ 1 đến L - 1 nằm trọn trong miền từ 1 đến R. Trừ chúng để giữ lại cả hai đầu L và R. Đặc biệt, khi L = 1, không có số dương nào bị trừ.

from math import lcm

def count_to(x, a, b):
    return x // a + x // b - x // lcm(a, b)

left, right, a, b = 5, 15, 3, 5
inside = count_to(right, a, b) - count_to(left - 1, a, b)
print("Thuộc ít nhất một lịch:", inside)
print("Không thuộc lịch nào:", right - left + 1 - inside)

Thuộc ít nhất một lịch: 6
Không thuộc lịch nào: 5

Độ dài đoạn là R - L + 1, không phải R - L. Nếu L chia hết cho một chu kỳ, dùng F(L) sẽ loại nhầm chính đầu trái. Nếu L = R, đoạn vẫn chứa một số để xét.

Mỗi truy vấn dùng hai lần tính lcm, nên chi phí là O(log max(a, b)). Với 1.000 truy vấn và chu kỳ không quá 100, lượng phép chia nhỏ so với việc duyệt một triệu ngày cho mỗi truy vấn.

Duyệt tập con khi có nhiều điều kiện

Với k nhóm, mỗi tập con (subset) khác rỗng xác định một giao. Giao của số lẻ nhóm được cộng; giao của số chẵn nhóm được trừ. Có 2^k - 1 tập con cần xét.

Vì sao dấu xen kẽ lại đúng? Giả sử một đối tượng thuộc đúng t nhóm. Nó xuất hiện trong C(t, j) giao có j nhóm. Tổng đóng góp là C(t, 1) - C(t, 2) + ...; theo nhị thức, tổng này bằng 1 khi t > 0. Đối tượng không thuộc nhóm nào đóng góp 0.

Bạn đã học cách dùng bit chọn tập con ở Bài 3. Trong đoạn sau, bit thứ i bật nghĩa là điều kiện thứ i tham gia giao. Chỉ số bắt đầu từ 0, còn mask = 0 được bỏ qua.

from math import lcm

def count_any(n, divisors):
    answer = 0
    k = len(divisors)
    for mask in range(1, 1 << k):
        common = 1
        for i, d in enumerate(divisors):
            if mask & (1 << i):
                common = lcm(common, d)
                if common > n:
                    break
        if common <= n:
            term = n // common
            answer += term if mask.bit_count() % 2 else -term
    return answer

print(count_any(100, [4, 6, 9]))

39

Khi common > n, giao không chứa bội dương trong miền. Thêm điều kiện chỉ giữ nguyên hoặc tăng lcm, nên có thể dừng xét giao đó. Dấu vẫn lấy từ toàn bộ mask; trong nhánh bỏ qua, số hạng bằng 0 nên dấu không ảnh hưởng kết quả. Lập luận này chỉ đúng với miền số dương: nếu miền chứa số 0, mọi giao đều có ít nhất phần tử 0 vì 0 chia hết cho mọi số dương.

Danh sách có số lặp hoặc một chu kỳ là bội của chu kỳ khác vẫn cho kết quả đúng. Tuy nhiên, các nhóm dư làm tăng số tập con. Có thể loại chúng trước khi duyệt nếu bạn chứng minh hợp không đổi.

Mỗi mặt nạ xét nhiều nhất k điều kiện. Bỏ qua chi phí số học trên số nguyên lớn, độ phức tạp là O(k * 2^k) phép tính lcm, bộ nhớ phụ O(1). Với k = 8, có 255 mặt nạ và nhiều nhất 2.040 lượt kiểm bit. Với k = 30, hơn một tỷ mặt nạ khiến cách duyệt này không phù hợp.

Chương trình sau kiểm chứng thuật toán trên miền nhỏ bằng cách liệt kê trực tiếp. Nó dùng cùng dữ liệu cho hai phương pháp:

from math import lcm
ds = [4, 6, 9]
n = 100
formula = 0
for mask in range(1, 1 << len(ds)):
    common = 1
    for i, d in enumerate(ds):
        if mask & (1 << i):
            common = lcm(common, d)
    formula += (1 if mask.bit_count() % 2 else -1) * (n // common)
direct = sum(any(x % d == 0 for d in ds) for x in range(1, n + 1))
print("Công thức:", formula)
print("Trực tiếp:", direct)

Công thức: 39
Trực tiếp: 39

Hai kết quả khớp nhau trên dữ liệu này. Một phép thử nhỏ không chứng minh mọi trường hợp, nhưng giúp tìm lỗi dấu hoặc lỗi tính giao. Lập luận theo đóng góp của từng đối tượng ở trên mới giải thích tính đúng tổng quát.

Lỗi thường gặp

Tóm tắt

• Cộng các nhóm rồi sửa giao giúp mỗi đối tượng trong hợp đóng góp một lần.
• Giao của các điều kiện chia hết được đếm bằng bội chung nhỏ nhất.
• Giao lẻ được cộng, giao chẵn được trừ khi duyệt tập con.
• Phần bù và hiệu F(R) - F(L - 1) xử lý câu hỏi phủ định và đoạn đóng.
• Kiểm tra số điều kiện trước khi chọn thuật toán có 2^k tập con.

Kiểm tra nhanh

Đọc thêm

• Tài liệu Python về math.gcd và math.lcm giải thích các hàm số nguyên.
• Tài liệu Python về phép toán trên tập hợp mô tả hợp và giao.