Thảo luận - Code xây dựng cấu hình bằng phương pháp sinh

algorithm
c++

(Đạt Phạm) #1

Đề bài: Nhập vào danh sách n bạn nam và n bạn nữ in tất cả các cách xếp 2n người đó vào 1 bàn tròn. Biết bạn nam và bạn nữ phải xếp xen kẽ nhau.

Phân tích
Giả sử mỗi cách xếp hoàn chỉnh 2n bạn là 1 cấu hình. Ta dùng số chẵn biểu diễn vị trí cho bạn nam và số lẻ biểu diễn vị trí cho bạn nữ.
- Khi xếp bạn nam

  • Vì mỗi ghế trống trong bàn tròn tương đương nhau. Bạn nam thứ n sẽ chỉ tạo ra 1 cách xếp cho cấu hình
  • Bạn nam thứ (n-1) sẽ tạo ra (n-1) cách xếp cho cấu hình
  • Bạn nam thứ (n-2) sẽ tạo ra (n-2) cách xếp cho cấu hình

    => Tương tự như vậy, khi xếp xong ta sẽ có tất cả (n-1)! cấu hình

- Khi xếp bạn nữ

  • Vì đã có 1 bạn nam thứ n làm mốc nên bạn nữ thứ n sẽ tạo ra n cách xếp cho cấu hình
  • Bạn nữ thứ (n-1) sẽ tạo ra (n-1) cách xếp cho cấu hình
  • Bạn nữ thứ (n-2) sẽ tạo ra (n-2) cách xếp cho cấu hình

    => Tương tự như vậy khi xếp xong ta sẽ có tất cả n! cấu hình
    Tóm lại: Ta có tất cả (n-1)!n! cấu hình

Thuật toán

  • Ta xây dựng một mảng coi như là 1 cái bàn tròn (vì khi ta uốn thẳng một đường tròn ra thì nó cũng tương tự nhau:grinning:)
  • Mảng có 2*k+2 phần tử (Dư 2 phần tử không in ra nhưng có tác dụng hỗ trợ cho thuật toán, cái này mình sẽ nói sau)
  • Ta sinh hoán vị các phần tử ở vị trí chẵn. Với mỗi phần tử ở vị trí chẵn ta sinh hoán vị tiếp n! cấu hình các phẩn tử ở vị trí lẻ.

Giờ mình sẽ quay lại giải thích cái 2 phần tử dư ra. Giờ bạn hãy nhớ lại bài toán sinh hoán vị n phần tử. Khi đó ta duyệt từ cuối lên đầu mảng để tìm đoạn cuối giảm dần dài nhất -> Chính yêu cầu này sẽ khiến bạn tạo dư ra 1 phần tử. Mà mình tạo ra 2 cái n như thế thì sẽ dư 2 phần tử

Code
Link: https://ideone.com/slxRKB

Trên đây là cách giải bài toán của mình theo phương pháp sinh. Bài toán hoàn toàn có thể giải bằng thuật toán quay lui nhá. Rất mong nhật được sự góp ý vè thuật toán cũng như tối ưu Code từ các pro.


(Red Sand) #2

Tiện thể có câu hỏi luôn. Mình có đọc qua phương pháp sinh, mình thấy các tài liệu đại học hay đề cập đến phương pháp này. Trước giờ mình toàn dùng Heap’s algorithm để tạo hoán vị, và mình không tìm thấy ưu điểm nào của phương pháp sinh để thay thế Heap’s, vậy tại sao phương pháp này lại phổ biến trong các tài liệu như vậy?


(Đạt Phạm) #3

Mình cũng thấy khó hiểu đoán đó ? Nhưng mà trình mình chịu không biết trả lời sao :sweat_smile:


(rogp10) #4

Bởi vì thuật toán đó có thể tạo hoán vị theo thứ tự từ điển.

Thực ra Heap hay SJT cũng là generator vì tạo cấu hình mới từ cấu hình ban đầu thôi :smiley:


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?