Bài 4 · Danh sách khác biệt và tập đóng

dCharm — tập đóng bằng danh sách khác biệt

dCharm chính là Charm, chỉ thay danh sách giao dịch bằng danh sách khác biệt. Nó vẫn dùng đúng bốn tình huống và vẫn cho ra bảy tập đóng như nhau; điểm khác duy nhất là cách nhận ra mỗi tình huống: thay vì so trực tiếp hai danh sách, ta nhìn xem danh sách khác biệt có rỗng hay không, rồi so độ phổ biến của hai bên.

1. Bốn tình huống nhìn qua danh sách khác biệt

Khi ghép một cặp, ta vẫn tính danh sách khác biệt của tập ghép như đã học, rồi so độ phổ biến của hai bên. Bốn tình huống của Charm được nhận ra như sau:

Tình huống một — hai danh sách giống hệt nhau

Nhận ra khi danh sách khác biệt rỗng và độ phổ biến hai bên bằng nhau. Khi đó gộp mặt hàng sau vào và bỏ nó khỏi danh sách.

Tình huống hai — danh sách của mặt hàng trước nằm gọn trong danh sách của mặt hàng sau

Nhận ra khi danh sách khác biệt rỗng nhưng độ phổ biến của mặt hàng trước nhỏ hơn của mặt hàng sau. Khi đó gộp mặt hàng sau vào nhưng vẫn giữ nó lại.

Tình huống ba — danh sách của mặt hàng sau nằm gọn trong danh sách của mặt hàng trước

Nhận ra khi danh sách khác biệt không rỗng nhưng độ phổ biến của tập ghép lại đúng bằng độ phổ biến của mặt hàng sau. Khi đó bỏ mặt hàng sau và mở một nhánh con mới.

Tình huống bốn — không bên nào chứa trọn bên nào

Là trường hợp còn lại: danh sách khác biệt không rỗng, và độ phổ biến của tập ghép nhỏ hơn cả hai bên. Khi đó giữ cả hai và mở một nhánh con mới.

Ở mức một, vì còn giữ danh sách giao dịch nên danh sách khác biệt của cặp hai mặt hàng chính là những giao dịch có ở mặt hàng đầu mà vắng ở mặt hàng sau. Quy tắc "nhánh con cũng được gộp thêm mặt hàng mới khi gặp tình huống một hoặc hai" vẫn giữ nguyên như bên Charm.

2. Giải mẫu từng bước

Vẫn bảng dữ liệu quen thuộc, ngưỡng phổ biến bằng ba, thứ tự xét là A, D, T, W rồi C. Độ phổ biến: A bốn, D bốn, T bốn, W năm, C sáu.

Nhánh mặt hàng A

Ghép A với D, rồi A với T.

Với AD: những giao dịch có A mà vắng D là 1 và 3, nên danh sách khác biệt gồm hai giao dịch; độ phổ biến bốn trừ hai còn hai, dưới ngưỡng nên loại. Với AT: chỉ giao dịch 4 có A mà vắng T, nên danh sách khác biệt gồm một giao dịch, độ phổ biến bốn trừ một còn ba. Danh sách khác biệt không rỗng, và độ phổ biến của tập ghép là ba lại khác với độ phổ biến của T (vốn là bốn), nên đây là tình huống bốn: ta mở nhánh con AT.

Ghép A với W.

Mọi giao dịch có A thì đều có W, nên danh sách khác biệt rỗng. Độ phổ biến của A là bốn, nhỏ hơn độ phổ biến của W là năm, nên đây là tình huống hai. Ta gộp W vào A, tập đang xét thành AW; đồng thời nhánh con AT cũng gộp thêm W, trở thành ATW.

Ghép AW với C.

Mọi giao dịch có AW thì đều có C, nên danh sách khác biệt rỗng. Độ phổ biến của AW là bốn, nhỏ hơn độ phổ biến của C là sáu, nên lại là tình huống hai. Ta gộp C vào, tập đang xét thành ACW độ phổ biến bốn; nhánh con ATW cũng gộp thêm C, thành ATWC. Khi đào sâu nhánh con, ta ghi nhận ACTW là tập đóng độ phổ biến ba, rồi ghi nhận ACW là tập đóng độ phổ biến bốn.

Các nhánh D, T, W và C

Nhánh D. Cặp DT có danh sách khác biệt gồm giao dịch 2 và 4, độ phổ biến hai nên loại. Cặp DW có danh sách khác biệt gồm giao dịch 6, độ phổ biến ba; vì khác biệt không rỗng mà độ phổ biến ba lại khác với độ phổ biến của W, nên là tình huống bốn, ta mở nhánh con DW. Cặp DC có danh sách khác biệt rỗng và độ phổ biến của D nhỏ hơn của C, là tình huống hai: gộp C để được CD, và nhánh con DW lớn lên thành DWC. Cuối nhánh, ta thu được CDW độ phổ biến ba và CD độ phổ biến bốn.

Nhánh T. Cặp TW có danh sách khác biệt gồm giao dịch 6, độ phổ biến ba, là tình huống bốn, mở nhánh con TW. Cặp TC có danh sách khác biệt rỗng và độ phổ biến của T nhỏ hơn của C, là tình huống hai: gộp C để được CT, nhánh con TW lớn lên thành TWC. Tập TWC bị ACTW bao trùm nên không được ghi lại. Cuối nhánh, ta chỉ thu được CT độ phổ biến bốn.

Nhánh W. Cặp WC có danh sách khác biệt rỗng và độ phổ biến của W nhỏ hơn của C, là tình huống hai: gộp C để được CW. Ta thu được CW độ phổ biến năm.

Nhánh C. Không còn gì để ghép, ta ghi nhận C độ phổ biến sáu.
Kết quả: bảy tập đóng, giống hệt Charm

C độ phổ biến sáu; CW năm; ACW bốn; CD bốn; CT bốn; CDW ba; và ACTW ba.

3. Bài tập tự luyện

Dùng bảng P, ngưỡng phổ biến bằng hai. Năm giao dịch: giao dịch một có B, C, M; giao dịch hai có B, E; giao dịch ba có B, C, E, M; giao dịch bốn có C, E, O; giao dịch năm có B, C, E, M. Sau khi loại O, thứ tự xét là M, B, C, E.

Bài một. Ghép M với B: danh sách khác biệt có rỗng không, và rơi vào tình huống nào?

M có ở các giao dịch 1, 3, 5; B có ở 1, 2, 3, 5. Mọi giao dịch có M thì đều có B, nên danh sách khác biệt rỗng. Độ phổ biến của M là ba, nhỏ hơn độ phổ biến của B là bốn, nên đây là tình huống hai: ta gộp B vào M, được tập MB.

Bài hai. Chạy dCharm cho bảng P và liệt kê bảy tập đóng.

Bảy tập đóng là: B độ phổ biến bốn; C bốn; E bốn; BE ba; CE ba; BCM ba; và BCEM hai. Kết quả này trùng đúng với Charm, vì danh sách khác biệt chỉ là cách tính khác chứ không đổi đáp số.