كيفية إنشاء جدول الدوري الرياضي تلقائيا

Question

سأبدأ بالقول إنني أفهم أن هذا الموضوع معقد وأنه ربما لا توجد إجابة سهلة.لو كان الأمر سهلاً لكان الجميع يفعله.ما قيل...

لقد طُلب مني إنشاء تطبيق لإدارة الدوري الرياضي.معظم المفاهيم سهلة الفهم إلى حد ما باستثناء هذا المفهوم:كيفية إنشاء جدول لعب لا يوجد فيه تداخلات (يلعب الفريق فريقين في وقت واحد)، حيث يلعب فريق في قسم ما مع فرقه مرتين ولكن يلعب مع فرق من الأقسام الأخرى مرة واحدة، ويتأكد من عدم وجود ثغرات في الجدول الجدول الزمني (يلعب كل فريق كل أسبوع)

تتم العملية حاليًا يدويًا باستخدام جدول بيانات من نوع حجر رشيد قمت بإنشائه لخدمة هذا الغرض، ولكنه يعمل فقط مع عدد الفرق التي تم تصميمه من أجلها.لدي اختلافات مخصصة لـ 30 فريقًا و24 فريقًا و28 فريقًا.بدلاً من محاولة إعادة ضبط جدول الترجمة باستمرار، أود أن أكون قادرًا على تدوين هذا المنطق وتعديل تلك العملية بدلاً من ذلك.

أفكار؟

Answer 1

هناك نظام واضح جدًا يستخدم على سبيل المثال.بطولات الشطرنج تسمى جولة روبن.

الفكرة هي تقسيم اللاعبين على جانبي الطاولة.تم تعيين أحد اللاعبين على أنه "محور" (للرغبة في الحصول على كلمة أفضل).تبدأ البطولة بجعل اللاعبين يواجهون بعضهم البعض ويلعبون ضد بعضهم البعض.بعد الجولة الأولى، يقوم الجميع باستثناء المحور بتحريك كرسي واحد للأمام ويتم تبديل الترتيب الأبيض/الأسود (المنزل/الخارج في الألعاب الرياضية).تنتهي المنافسة الكاملة عندما يجلس اللاعبون في أماكنهم الأصلية.إذا كنت تريد من الجميع أن يلعبوا الجميع مرتين، فما عليك إلا أن تفعل الشيء نفسه مرة أخرى.

مقالة ويكيبيديا مع تفاصيل التنفيذ

في حالتك الخاصة، سأحاول إجراء جولة روبن مرة واحدة بما في ذلك جميع الفرق.ثم تفعل الشيء نفسه لكل قسم مرة واحدة وللتأكد من أن الفرق داخل الأقسام تلعب بعضها البعض مرة واحدة على أرضها ومرة ​​خارج أرضها، تحقق من الجولة الأولى من روبن من الطريقة التي لعبت بها الفرق في تلك الجولة.

الجانب السلبي لهذا، بالطبع، هو أنك ستلعب جميع المباريات بين الأقسام قبل انتهاء البطولة بوقت طويل (نظرًا لأن آخر مباريات n-1 كانت ضد فرق داخل القسم [n=عدد الفرق في القسم]).إذا كانت هذه مشكلة، فيمكنك ببساطة تبديل المباريات قليلاً.

لقد قمت بالفعل بكتابة نص بايثون بسيط يقوم بذلك.لم يستغرق الأمر عدة أسطر من التعليمات البرمجية وحقق نتائج جيدة جدًا.سيؤدي هذا إلى إنشاء جدول زمني حيث يلعب كل فريق مع كل فريق في قسمه مرتين ومرة ​​ضد فرق في أقسام أخرى.ومع ذلك، لا يوجد فحص للتأكد من أن الفريقين يلتقيان مرتين بحيث يكون نفس الفريق في المنزل.ولكن يجب أن يعطي هذا الرمز فكرة جيدة عن كيفية إنشاء رمز الجدولة الخاص بك.

#!/usr/bin/python

div1 = ["Lions", "Tigers", "Jaguars", "Cougars"]
div2 = ["Whales", "Sharks", "Piranhas", "Alligators"]
div3 = ["Cubs", "Kittens", "Puppies", "Calfs"]

def create_schedule(list):
    """ Create a schedule for the teams in the list and return it"""
    s = []

    if len(list) % 2 == 1: list = list + ["BYE"]

    for i in range(len(list)-1):

        mid = int(len(list) / 2)
        l1 = list[:mid]
        l2 = list[mid:]
        l2.reverse()    

        # Switch sides after each round
        if(i % 2 == 1):
            s = s + [ zip(l1, l2) ]
        else:
            s = s + [ zip(l2, l1) ]

        list.insert(1, list.pop())

    return s


def main():
    for round in create_schedule(div1):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div2):
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div3): 
        for match in round:
            print match[0] + " - " + match[1]
    print
    for round in create_schedule(div1+div2+div3): 
        for match in round:
            print match[0] + " - " + match[1]
        print

if __name__ == "__main__":
    main()

Answer 2

هناك نوعان من الخوارزميات ، واحدة للفرق الفردية ، واحدة حتى للفرق للتأكد من حدوث جولة روبن.

سأقوم بإنشاء رسم لك إذا استطعت.

# فردية من الفرق

الخوارزمية هي تدوير جميع الفرق في اتجاه عقارب الساعة. إذا كان لدينا 5 فرق:

1 2 --> 3 1 --> 5 3 --> 4 5 --> 2 4
3 4     5 2     4 1     2 3     1 5
5       4       2       1       3   

في هذه المرحلة ، أكملنا جولة واحدة روبن حيث يلعب الجميع بعضهم البعض مرة واحدة ... ستكون الجولة التالية مرة أخرى ..

1 2
3 4
5

حتى # من الفرق

عندما يكون لدينا عدد زوجي من الفرق ، فإنك تفعل نفس التناوب ، باستثناء أنك تعقد الفريق رقم 1 في وضع ثابت وتدوير جميع الفرق الأخرى حول المرتبة الأولى بطريقة عقارب الساعة. لذلك ، إذا كان لدينا 4 فرق ..

1 2 --> 1 3 --> 1 4 
3 4     4 2     2 3 

ستكون هذه جولة واحدة كاملة روبن ... ستكون المباراة التالية ..

1 2 
3 4 

برمجيا ، هناك بعض الطرق التي يمكنك من خلالها التعامل مع هذا. ربما الرمز المنشور أعلاه يفعل نفس الشيء لول ..

Answer 3

أود فقط تشفير هذه القيود كصيغة منطقية واستخدام بعض القالب SAT للحصول على حلول (على سبيل المثال Minisat لـ C ++ ، SAT4J لـ Java ، ويمكنك حتى أن تكتب لك محللاً بسيطًا). يتم استئصال المدخلات إلى هذه الحلول بواسطة DIMACs.

راجع أيضًا "A SAT تشفير لمشكلة لاعب الجولف الاجتماعي" و "جدولة مقرها SAT لجداول البطولة" لاتفاقيات SAT من المشكلات المماثلة.

Answer 4

هذه لقطة في التنفيذ

public interface ITeam
{
   bool PlaysOn(DateTime date);
   bool canPlay(ITeam); //returns true if a game between the teams is legal (played once/twice   
                        //already, same different divisions and other applicable rules
}

IEnumerable<ITeam> teams = null; //replace with initialization
IEnumerable<ITeams> reversed = team.Reverse();
IEnumerable<DateTIme> gameDays = null;//replace with initialization
var count = teams.Count();

foreach(var date in gameDays)
{
   for(int i = 0;i<count;i++)
   {
      var innerTeams = i % 2 == 0 ? teams : reversed;
      var team = (from t in innerTeams
                  where !t.PlaysOn(date)
                  select t).First();  
      var opp = (from t in teams
                 where !t.PlaysOn(date) && t.CanPlay(team)
                 select t).First();
      SetupGame(team,opp);
   }
} //lot of optimazation possible :)

لقد اختبرته فقط على الورق ولكن لإعداداتي ، فهي تعمل. من خلال التناوب بين البدء في بداية قائمة الفرق ونهاية القائمة ، أتجنب المواقف التي يتعين على الفريق نفسه أن يلعبها نفس الفريق مرارًا وتكرارًا (أو تلعب مرارًا وتكرارًا في نفس اليوم) في اختبار الورق I يمثل كل لقاء ممكن باعتباره Opponnent مختلف ولكن هذا هو في الأساس ما ينبغي أن تفعله طريقة العلل. آمل أن يساعد هذا ، رغم أنه ليس حلاً كاملاً