Kata learns to code

Những ai đam mê lập trình và thuật toán hẳn có nhiều lúc ngây ngất trước vẻ đẹp của các thuật toán cũng như sự tinh tế trong cách cài đặt chúng! Có nhiều bài toán nghĩ ra thuật toán rất khó nhưng nghĩ ra rồi thì cài đặt lại rất dễ. Lại có những bài ngược lại, thuật toán thì thấy ngay nhưng để biểu diễn cho máy nó hiểu thì khó vô cùng. Lại cũng có những bài “quái chiêu” cả thuật toán lẫn cài đặt đều khó nhăn răng và 1 trong số đó là bài toán kinh điển Hôn Nhân Bền Vững tôi muốn giới thiệu cùng các bạn.

Phát biểu bài toán nghe khá hấp dẫn: có N chàng trai và N cô gái, mỗi chàng trai phát biểu cảm nghĩ về N cô gái kia (rằng là cô này anh ta thích nhất, cô này thích nhì, ba, … cho đến cô thích thứ N) tương tự các cô gái cũng phát biểu như vậy về các chàng trai. Hãy ghép đôi họ với nhau sao cho các cuộc hôn nhân này là bền vững nghĩa là không được tồn tại 2 cặp mà người chồng bên cặp này lại thích người vợ bên cặp kia hơn vợ mình, đồng thời người vợ bên cặp kia lại cũng thích người chồng bên cặp này hơn chồng mình, khi đó 2 người này sẽ tìm đến với nhau và thế là ngoại tình.

Bây giờ chúng ta sẽ nghiên cứu 1 thuật toán xây dựng các cặp bền vững dựa trên ý tưởng giống như đời thực của bài toán. Mỗi chàng trai X sẽ chọn cho mình 1 cô dâu, hiển nhiên là anh ta sẽ chọn cô gái đầu tiên trong danh sách của mình. Nếu cô này đã hứa hôn (đã được chọn trước đó) với chàng trai khác mà cô ta thích hơn thì anh chàng X phải chọn người phụ nữ kế tiếp trong danh sách của anh ta, quá trình này tiếp tục cho đến khi X tìm được một cô Y chưa được hứa hôn hoặc thích anh ta hơn anh chàng đã hứa hôn trước đó. Nếu Y chưa được hứa hôn thì cô ta sẽ được gả cho X và chúng ta tiếp tục cho người đàn ông kế tiếp. Còn nếu Y đã hứa hôn thì sẽ hủy bỏ cuộc đính hôn và gả cô ta cho X (vì cô ta thích X hơn), và chúng ta lại tiếp tục với anh chàng vừa bị từ hôn.

Phương pháp này có lẽ được mô phỏng từ 1 câu chuyện trong các tiểu thuyết của thế kỉ 19. Rất đơn giản phải không? Nhưng còn cài đặt thì sao? Trong các tài liệu thường thấy ở VN thì họ dùng foward bởi phải xây dựng 2 hàm mà trong thân hàm này gọi tới hàm kia, rất rối rắm phức tạp, khó sửa lỗi và code cũng dài dòng. Còn trong cuốn Cẩm Nang Thuật Toán (sách dịch nước ngoài) tập 2, tác giả đã có 1 cách cài đặt vô cùng đỉnh cao, gọn nhẹ và xúc tích, (điều thường thấy trong bộ sách này) chẳng phải pho goắc pho ghiếc gì hết.

Bởi vì tất cả các danh sách sở thích đều co chung độ dài, cài đặt đơn giản nhất là dùng mảng 2 chiều. Ví dụ prefer[m, w] là cô gái thứ w trong danh sách sở thích của chàng trai thứ m. Hơn nữa chúng ta cần theo dõi xem mỗi chàng trai đã xử lí đến đâu trong danh sách anh ta. Điều nay có thể được thực hiện bằng 1 mảng 1 chiều next, mảng này khởi tạo đến 0 và next[m] + 1 là chỉ số của cô gái kế tiếp trong danh sách của chàng trai thứ m, chỉ danh của cô tra sẽ là prefer[m, next[m] + 1]. Với mỗi cô gái ta cần theo dõi vị hôn phu hiện thời là ai (fiancee[w] sẽ là chàng trai đã hứa hôn với cô gái w) và chúng ta cần trả lời câu hỏi ” người đàn ông thứ s có được thích hơn so với người đàn ông fiancee[w] hay không?”. Câu trả lời này có thể được giải đáp bằng cách tìm kiếm tuần tự cho tới khi s hoặc fiancee[w] được tìm thấy, nhưng cách này không hiệu quả nếu 2 người nằm ở cuối danh sách. Thay vì vậy, chúng ta dùng 1 danh sách ngược: rank[w, s] là chỉ số của chàng trai thứ s trong danh sách sở thích của cô w. Sự phù hợp của vị hôn phu s có thể xác định rất nhanh chóng bằng cách kiểm tra xem rank[w, s] có nhỏ hơn rank[w, fiancee[w]] hay không. Các mảng này được xây dựng dễ dàng và trực tiếp từ danh sách các sở thích. Để khởi đầu, chúng ta dùng 1 lính canh là chàng trai 0 để khởi tạo cho vị hôn phu và đặt anh ta ở cuối tất cả các danh sách sở thích của các cô gái.

Với cấu trúc dữ liệu được khởi tạo bằng phương pháp này, việc cài đặt có thể thực hiện dễ dàng như sau:

Language: Pascal
Author: Katatunix

for m := 1 to N do
begin
    s := m;
    repeat
        next[s] := next[s] + 1;
        w := prefer[s, next[s]];
        if rank[w, s] < rank[w, fiancee[w]] then
        begin
            t := fiancee[w]; fiancee[w] := s; s := t;
        end;
    until s = 0;
end;