Mô phỏng thuật toán Liệt kê tập con (bitmask)

Subset Enumeration (Bitmask) · Nhóm: Bit & Mặt nạ

Với tập n phần tử, mỗi số mask trong 0..2^n-1 mã hoá một tập con · bit j của mask bằng 1 nghĩa là phần tử thứ j được chọn.

Ý tưởng

Duyệt mask chạy từ 0 tới 2^n-1, mỗi mask ứng với đúng một tập con.

Với từng mask, xét từng bit j: nếu mask & (1<<j) khác 0 thì thêm phần tử thứ j vào tập con.

In tập con ứng với mask rồi sang mask kế tiếp, không lặp lại và không bỏ sót.

Vì sao đúng

Bitmask cho một thứ tự cố định, không trùng và không sót, biến việc liệt kê tập con thành đếm nhị phân đơn giản.

Mã Python

def subsets(elements):
    n = len(elements)
    for mask in range(1 << n):        # every mask 0..2^n-1
        subset = []
        for j in range(n):            # test each bit
            if mask & (1 << j):       # bit j is set
                subset.append(elements[j])
        yield subset

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.