राउंड-रॉबिन टूर्नामेंट के लिए शेड्यूलिंग एल्गोरिदम?

Question

मैंने हाल ही में सामान का अध्ययन किया और डोनाल्ड Knuth के साथ मिलकर काम किया। लेकिन मुझे अपनी समस्या के लिए सही एल्गोरिदम नहीं मिला।

समस्या हमारे पास एन प्लेयर के साथ एक लीग है। हर हफ्ते उनके पास एक दूसरे के साथ एक मैच होता है। एन-1 सप्ताह में प्रत्येक टीम एक-दूसरे के खिलाफ लड़ी। दिन में एन/2 मैच होते हैं। लेकिन एक टीम केवल सप्ताह में एक बार लड़ सकती है। अगर हम एक (एन/के) संयोजन उत्पन्न करते हैं तो हम सभी संयोजन प्राप्त करते हैं ... (मानते हैं कि = 2) लेकिन मुझे उन्हें सही क्रम में लाने की आवश्यकता है।

मेरा पहला सुझाव था ... सबसे अच्छा नहीं। मैंने अभी एक सरणी बनाई है, और उसके बाद कंप्यूटर को सही तरीके से खोजने का प्रयास करने दें। यदि नहीं, तो शुरुआत में वापस जाएं, सरणी को घुमाएं और फिर से करें, ठीक है, मैंने इसे PHP (n = 8) में प्रोग्राम किया है और क्या काम आता है, लेकिन कई बार लेते हैं, और n = 16 के लिए यह मुझे टाइमआउट देता है भी।

तो मैंने सोचा कि शायद हमें एक एल्गोरिदम मिल जाए, या कोई भी इस पुस्तक को कवर करने वाली पुस्तक जानता है।

और यहाँ मेरे कोड है: http://pastebin.com/Rfm4TquY

Answer 1

क्लासिक एल्गोरिथ्म इस तरह काम करता है:

संख्या टीमों 1..n। (यहां मैं एन = 8 ले जाऊंगा।)

सभी पंक्तियों को दो पंक्तियों में लिखें।

1 2 3 4 
8 7 6 5 

कॉलम दिखाते हैं कि कौन सी टीम उस दौर में खेलेंगे (1 बनाम 8, 2 बनाम 7, ...)।

अब, 1 तय रखें, लेकिन सभी अन्य टीमों को घुमाएं। सप्ताह 2 में, आप

1 8 2 3 
7 6 5 4 

हो और 3 सप्ताह में, आप

1 7 8 2 
6 5 4 3 

इस के माध्यम से सप्ताह n-1, इस मामले में जारी है मिलता है,

1 3 4 5 
2 8 7 6 

हैं n विषम है , वही काम करें लेकिन एक डमी टीम जोड़ें। जो भी डमी टीम के खिलाफ मेल खाता है वह उस सप्ताह bye प्राप्त करता है।