Câu hỏi Lập kế hoạch thuật toán cho một giải đấu round-robin?


Gần đây tôi đã nghiên cứu công cụ và gặp gỡ Donald Knuth. Nhưng tôi đã không tìm thấy thuật toán đúng cho vấn đề của tôi.

Vấn đề Chúng tôi có một giải đấu với n người chơi. mỗi tuần họ có một trận đấu với nhau. trong n-1 tuần mỗi đội chiến đấu với nhau. có n / 2 phù hợp với một ngày. nhưng một đội chỉ có thể chiến đấu một lần trong một tuần. nếu chúng ta tạo ra một kết hợp (n / k) chúng ta có được tất cả các kết hợp ... (giả sử k = 2) nhưng tôi cần phải mang chúng theo đúng thứ tự.

Đề nghị đầu tiên của tôi là ... không phải là gợi ý tốt nhất. tôi vừa tạo một mảng, và sau đó để máy tính thử nếu anh ta tìm đúng cách. nếu không, hãy quay lại bắt đầu, trộn các mảng và làm lại, tốt, tôi đã lập trình nó trong PHP (n = 8) và những gì xuất hiện, nhưng mất nhiều thời gian, và cho n = 16 nó cho tôi thời gian chờ cũng.

Vì vậy, tôi nghĩ nếu chúng ta có thể tìm thấy một thuật toán, hoặc bất cứ ai biết một cuốn sách bao gồm vấn đề này.

Và đây là mã của tôi: http://pastebin.com/Rfm4TquY


10
2017-07-11 10:01


gốc


Xem Wikipedia - Gareth Rees


Các câu trả lời:


Thuật toán cổ điển hoạt động như sau:

Số đội 1..n. (Ở đây tôi sẽ lấy n = 8.)

Viết tất cả các đội trong hai hàng.

1 2 3 4
8 7 6 5

Các cột cho thấy đội nào sẽ chơi trong vòng đó (1 vs 8, 2 vs 7, ...).

Bây giờ, giữ 1 cố định, nhưng xoay tất cả các đội khác. Trong tuần 2, bạn nhận được

1 8 2 3
7 6 5 4

và trong tuần thứ 3, bạn sẽ nhận được

1 7 8 2
6 5 4 3

Điều này tiếp tục qua tuần n-1, trong trường hợp này,

1 3 4 5
2 8 7 6

Nếu n là lẻ, làm điều tương tự nhưng thêm một đội giả. Bất kỳ ai phù hợp với đội giả đều nhận được tạm biệt tuần đó.


39
2017-07-11 11:56