Bài 14: Set và phép toán tập hợp

Sau bài này bạn sẽ:

• Biết set là gì, khác list / tuple / dict ở điểm nào.
• Tạo set và phân biệt với empty dict.
• Thêm / xóa phần tử với add, update, remove, discard, pop, clear.
• Dùng được 4 phép toán tập hợp: union, intersection, difference, symmetric difference.
• Kiểm tra quan hệ subset / superset / disjoint.
• Hiểu khi nào dùng frozenset thay vì set thường.
• Loại duplicate khỏi list và biết pitfall mất thứ tự.

Bài chạy trên Python 3.8 trở lên.

Set là collection có 4 đặc tính:

• Unordered — không có thứ tự, không index được bằng s[0].
• Unique — không chứa phần tử trùng, thêm trùng sẽ bị bỏ qua.
• Mutable — có thể thêm / xóa phần tử sau khi tạo.
• Phần tử phải hashable — số, chuỗi, tuple thì được; list, dict, set thì không.

Set trong Python dựng trên hash table, gần như tương ứng với khái niệm tập hợp trong toán học.

s = {3, 1, 2, 2, 3}
print(s)           # {1, 2, 3} — duplicate tự loại
print(len(s))      # 3
print(type(s))     # <class 'set'>

# Không index được — set không có thứ tự
# s[0]   # TypeError: 'set' object is not subscriptable

Phần tử của set phải hashable:

{1, "hello", (1, 2)}        # OK — int, str, tuple đều hashable
# {1, [2, 3]}                # TypeError: unhashable type: 'list'
# {1, {"a": 1}}              # TypeError: unhashable type: 'dict'

Có 2 cách tạo set:

# Cách 1: literal với dấu {}
s1 = {1, 2, 3}

# Cách 2: hàm set() — chuyển từ iterable
s2 = set([1, 2, 3])
s3 = set("hello")           # {'h', 'e', 'l', 'o'} — duplicate 'l' bị loại
s4 = set(range(5))          # {0, 1, 2, 3, 4}

Lưu ý quan trọng về empty set:

empty_set = set()           # ✅ đây mới là empty set
empty_dict = {}             # ❌ đây là empty DICT, không phải set

print(type(empty_set))      # <class 'set'>
print(type(empty_dict))     # <class 'dict'>

Dấu {} được Python dành riêng cho dict vì lý do lịch sử (dict ra trước set). Muốn set rỗng phải gọi set().

Thêm phần tử:

s = {1, 2, 3}

s.add(4)                # thêm 1 phần tử
print(s)                # {1, 2, 3, 4}

s.add(2)                # đã có rồi — không thay đổi
print(s)                # {1, 2, 3, 4}

s.update([5, 6, 7])     # thêm nhiều phần tử từ iterable
print(s)                # {1, 2, 3, 4, 5, 6, 7}

s.update({8, 9}, [10])  # update nhận nhiều iterable
print(s)                # {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Xóa phần tử — 3 cách với hành vi khác nhau khi không tìm thấy:

s = {1, 2, 3}

s.remove(2)             # xóa 2 — OK
# s.remove(99)          # KeyError: 99 — raise khi không tồn tại

s.discard(3)            # xóa 3 — OK
s.discard(99)           # 99 không có, KHÔNG raise — im lặng bỏ qua

x = s.pop()             # xóa và trả về 1 phần tử "bất kỳ"
print(x)                # ví dụ: 1 (không đoán được phần tử nào)

s.clear()               # xóa hết
print(s)                # set()

Quy tắc chọn: dùng remove khi bạn chắc phần tử tồn tại (muốn lỗi nếu sai), dùng discard khi không chắc.

Lý do quan trọng nhất để dùng set: kiểm tra phần tử có thuộc collection hay không (membership test) bằng toán tử in rất nhanh — trung bình O(1) thay vì O(n) như list.

s = {1, 2, 3, 4, 5}
print(3 in s)           # True
print(99 in s)          # False
print(99 not in s)      # True

So sánh tốc độ với list:

import time

n = 1_000_000
my_list = list(range(n))
my_set  = set(my_list)

target = n - 1          # phần tử cuối — trường hợp xấu cho list

t0 = time.perf_counter()
_ = target in my_list   # O(n) — duyệt từ đầu
t1 = time.perf_counter()
_ = target in my_set    # O(1) — tra hash
t2 = time.perf_counter()

print(f"list: {t1 - t0:.6f}s")    # vài chục ms
print(f"set:  {t2 - t1:.6f}s")    # vài micro giây

Với 1 triệu phần tử, set có thể nhanh hơn list hàng nghìn lần cho 1 phép kiểm tra. Khi bạn cần kiểm tra membership nhiều lần trên cùng 1 collection, convert sang set một lần là rất đáng.

Set hỗ trợ 4 phép toán tập hợp như trong toán học, mỗi phép có 2 dạng: toán tử và method.

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

Union — hợp, lấy tất cả phần tử của cả 2 set:

print(a | b)            # {1, 2, 3, 4, 5, 6}
print(a.union(b))       # {1, 2, 3, 4, 5, 6}

Intersection — giao, lấy phần tử có ở cả 2 set:

print(a & b)            # {3, 4}
print(a.intersection(b))  # {3, 4}

Difference — hiệu, phần tử có trong a nhưng không có trong b:

print(a - b)            # {1, 2}
print(a.difference(b))  # {1, 2}
print(b - a)            # {5, 6} — không đối xứng!

Symmetric difference — hiệu đối xứng, phần tử ở 1 trong 2 set nhưng không phải cả 2:

print(a ^ b)                       # {1, 2, 5, 6}
print(a.symmetric_difference(b))   # {1, 2, 5, 6}

Khác biệt giữa toán tử và method: toán tử (|, &, -, ^) yêu cầu cả 2 vế phải là set; method chấp nhận mọi iterable:

a = {1, 2, 3}
print(a.union([3, 4, 5]))    # {1, 2, 3, 4, 5} — OK với list
# print(a | [3, 4, 5])       # TypeError

Tất cả phép trên có dạng in-place (sửa luôn set bên trái) bằng cách thêm =: a |= b, a &= b, a -= b, a ^= b — tương ứng với update, intersection_update, difference_update, symmetric_difference_update.

Ngoài 4 phép toán, set còn cho phép kiểm tra quan hệ giữa 2 tập:

a = {1, 2}
b = {1, 2, 3, 4}

# Subset — a có phải tập con của b?
print(a <= b)              # True
print(a.issubset(b))       # True

# Strict subset — a là tập con thực sự (a ≠ b)
print(a < b)               # True
print(b < b)               # False — bằng nhau không tính

# Superset — b có chứa a?
print(b >= a)              # True
print(b.issuperset(a))     # True

# Disjoint — 2 set không có phần tử chung?
print({1, 2}.isdisjoint({3, 4}))   # True
print({1, 2}.isdisjoint({2, 3}))   # False

Quan hệ này hay được dùng trong feature engineering, ví dụ kiểm tra "tập feature người dùng chọn có nằm trong tập feature hợp lệ không".

frozenset là phiên bản immutable của set: tạo xong không thêm / xóa được. Đổi lại, nó hashable, nghĩa là có thể làm key của dict hoặc phần tử của set khác.

fs = frozenset([1, 2, 3])
print(fs)               # frozenset({1, 2, 3})

# fs.add(4)             # AttributeError — không có method add

# Vẫn đọc và làm phép toán được
print(2 in fs)          # True
print(fs | {3, 4})      # frozenset({1, 2, 3, 4})

Set thường không hashable nên không nằm được trong set khác:

# {{1, 2}, {3, 4}}                    # TypeError: unhashable type: 'set'
nested = {frozenset({1, 2}), frozenset({3, 4})}   # OK
print(nested)

Dùng frozenset khi cần một tập hợp "cố định" để làm key (ví dụ: gom các feature cùng nhóm), hoặc khi muốn bảo đảm caller không sửa.

Tương tự list, set cũng có dạng comprehension — viết set bằng một biểu thức ngắn:

# Tập bình phương các số 0..9
squares = {x * x for x in range(10)}
print(squares)          # {0, 1, 4, 9, 16, 25, 36, 49, 64, 81}

# Tập các ký tự thường có trong chuỗi (loại trùng)
letters = {c.lower() for c in "Hello World" if c.isalpha()}
print(letters)          # {'h', 'e', 'l', 'o', 'w', 'r', 'd'}

Bài 15 sẽ học chi tiết về comprehension (list / set / dict) — cú pháp, khi nào dùng, khi nào không nên.

1. Loại duplicate khỏi list:

nums = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(nums))
print(unique)           # ví dụ [1, 2, 3, 4] — thứ tự không đảm bảo

2. Membership test nhanh trong collection lớn:

stopwords = {"the", "a", "an", "is", "in", "of", "and"}

text = "this is an example of cleaning text"
tokens = [w for w in text.split() if w not in stopwords]
print(tokens)           # ['this', 'example', 'cleaning', 'text']

3. Tìm phần tử chung giữa 2 dataset:

users_a = {"alice", "bob", "carol", "dave"}
users_b = {"bob", "dave", "eve", "frank"}

common = users_a & users_b
only_a = users_a - users_b
print(common)           # {'bob', 'dave'}
print(only_a)           # {'alice', 'carol'}

4. Tag / label system trong ML:

# Mỗi sample có một tập label (multi-label classification)
sample_labels = {"cat", "indoor", "small"}
required      = {"cat"}
forbidden     = {"dog"}

ok = required.issubset(sample_labels) and sample_labels.isdisjoint(forbidden)
print(ok)               # True

5. Đếm số phần tử duy nhất:

words = "to be or not to be that is the question".split()
print(len(set(words)))  # 8 — số từ phân biệt

Cạm bẫy hay gặp khi mới học set: dùng set() để loại duplicate nhưng cần giữ thứ tự xuất hiện:

items = ["b", "a", "c", "a", "b", "d"]
print(list(set(items)))     # ví dụ ['d', 'b', 'a', 'c'] — thứ tự không đoán được

Nếu cần loại duplicate và giữ thứ tự ban đầu, dùng dict.fromkeys — dict trong Python 3.7+ giữ thứ tự chèn:

items = ["b", "a", "c", "a", "b", "d"]
unique_ordered = list(dict.fromkeys(items))
print(unique_ordered)       # ['b', 'a', 'c', 'd'] — đúng thứ tự lần đầu xuất hiện

Lý do: dict ghi nhớ thứ tự thêm key, mà fromkeys bỏ qua key trùng. Đây là idiom chuẩn để "dedupe stable" trong Python hiện đại.

Ngoài ra: hash của một số kiểu (đặc biệt là str) bị Python randomize giữa các lần chạy vì lý do bảo mật. Đừng dựa vào "thứ tự khi in set" — nó có thể đổi giữa các lần chạy chương trình.

Bài 1: Phần tử chung giữa 2 list.

Viết hàm common_elements(list_a, list_b) nhận 2 list, trả về list các phần tử có ở cả 2 (không duplicate). Yêu cầu dùng set bên trong. Test:

print(common_elements([1, 2, 2, 3, 4], [3, 4, 4, 5, 6]))
# kết quả mong đợi (thứ tự có thể khác): [3, 4]

Bài 2: Hai chuỗi có ký tự chung không?

Viết hàm share_letter(s1, s2) trả về True nếu 2 chuỗi có ít nhất một ký tự chung (so sánh phân biệt hoa thường), ngược lại False. Gợi ý: isdisjoint. Test:

print(share_letter("hello", "world"))   # True (chung 'l', 'o')
print(share_letter("abc", "xyz"))       # False

Bài 3: Dedupe giữ thứ tự.

Viết hàm dedupe(items) nhận một list, trả về list đã loại duplicate nhưng giữ nguyên thứ tự lần đầu xuất hiện. So sánh kết quả khi dùng set trực tiếp và khi dùng dict.fromkeys.

Bài 4 (mở rộng): viết hàm jaccard(s1, s2) tính Jaccard similarity giữa 2 set theo công thức |A ∩ B| / |A ∪ B|. Trả về 0.0 khi cả 2 set đều rỗng. Đây là độ đo phổ biến cho similarity giữa các tập tag trong ML.

• Set là collection unordered, unique, mutable; phần tử phải hashable.
• Tạo bằng {1, 2, 3} hoặc set([...]). Empty set là set() — {} là dict.
• Thêm: add (1 phần tử), update (nhiều). Xóa: remove (raise nếu thiếu), discard (im lặng), pop, clear.
• Membership test x in s là O(1) trung bình — nhanh hơn list nhiều khi collection lớn.
• 4 phép toán tập hợp: | union, & intersection, - difference, ^ symmetric difference (kèm method union, intersection, ... linh hoạt hơn).
• Quan hệ: <= / issubset, >= / issuperset, isdisjoint.
• frozenset là set immutable, hashable — dùng được làm dict key hoặc phần tử của set khác.
• Set comprehension {expr for x in iterable} — chi tiết ở bài 15.
• Set không giữ thứ tự: muốn dedupe + giữ thứ tự, dùng dict.fromkeys.

Bài tiếp theo sẽ học list comprehension — cách viết list (và set / dict) ngắn gọn bằng 1 biểu thức, kết hợp với filter và transform.