טורניר ליגה – כולם נגד כולם

11/04/2015

אין תגובות

קצת TSQL וקצת מתימטיקה: יש לנו ליגה בת 14 קבוצות, ואנחנו רוצים להכין תוכנית משחקים בת 14-1=13 סיבובים, בה בכל סיבוב מתקיימים 14/2=7 משחקים, כל קבוצה משחקת משחק אחד בכל סיבוב, וכל קבוצה משחקת פעם אחת נגד כל כל קבוצה אחרת במהלך כל הטורניר.
למשל- טבלת ליגת העל נכון למועד כתיבת שורות אלו (מה שחשוב מבחינתנו אינו סדר הקבוצות אלא רשימת הקבוצות, כלומר- טבלה במשמעותה ה-SQL-ית):

Create Table #T(ID Int Primary Key Clustered,

                    Name NVarchar(20));

 

Insert

Into    #T

Values    (1,N'מכבי ת"א'),

        (2,N'הפועל ב"ש'),

        (3,N'עירוני ק"ש'),

        (4,N'בית"ר ירושלים'),

        (5,N'מכבי פ"ת'),

        (6,N'מכבי חיפה'),

        (7,N'הפועל רעננה'),

        (8,N'מכבי נתניה'),

        (9,N'בני סכנין'),

        (10,N'הפועל ת"א'),

        (11,N'מ.ס. אשדוד'),

        (12,N'הפועל חיפה'),

        (13,N'הפועל פ"ת'),

        (14,N'הפועל עכו');

יתכנו מצבים של טורניר בו מספר הקבוצות אינו זוגי, ואזי נוסיף קבוצת דמה שכל קבוצה שתשובץ נגדה – תהיה חופשייה באותו סיבוב.
סקירה לגבי הנושא ומספר אלגוריתמים לפתרון הבעייה נמצא בוויקיפדיה באנגלית.
חסר לי שם פתרון אחד אותו זכרתי במעורפל עוד מהיסודי, כשלמדנו לחשב “לוח חיבור מודולרי” בו במקום תוצאת החיבור של שני מספרים מופיעה השארית שלהם מחלוקה במספר נתון (בדרך כלל מספר המספרים בלוח עצמו).
למשל, לוח החיבור המודולרי של 14:

image

(נניח- 10+13=23, והשארית מחלוקה ב-14 היא 9)
כעקרון זה נראה כיוון נכון: כל מספר מופיע פעם אחת בכל שורה ובכל עמודה, הטבלה סימטרית ולכן 3 נגד 4 ו-4 נגד 3 יהיו שניהם במחזור 7', וכל מספר מחזיר שארית אחרת עם כל מספר אחר וכו’.
מה הבעייה? צריך ליצור לוח חיבור מודולרי ל-14 קבוצות ולחשב שארית מחלוקה ב-13 כדי שנקבל 13 מחזורים שונים (0..12) ולא 14 מחזורים (0..13).
ננסה שוב:

image

הבעיות כעת הן שתיים:

  1. שורה\עמודה 14 זהה לשורה\עמודה 1 כי שתיהן שוות 1 בחשבון מודולרי.
  2. לאורך האלכסון היורד משמאל לימין מופיעים משחקים עצמיים שלא יתקיימו: 1 נגד 1, 2 נגד 2 וכו’.

אפשר כבר לחשוב על פתרון התופס שתי ציפורים ביד אחת- את המחזור המופיע באלכסון נמחק ונעביר לשורה\עמודה 14:

image

כעת הכל נראה בסדר: כל אחד מהמספרים 0..12 מופיע פעם אחת בכל שורה\עמודה (כלומר- כל קבוצה משחקת נגד כל השאר וכל משחק בסיבוב אחר), ונובע מכך שכל מספר מחזור מופיע 13 פעמים.

ומכאן ל-TSQL- כל משחק יתקיים במחזור שהוא השארית של סכום מספרי הקבוצות, חוץ מקבוצה 14 (הפועל עכו.. ליבי ליבי עליכם!) שתשחק נגד כל קבוצה במחזור בו היא הייתה אמורה לשחק נגד עצמה (ה-Iif המקונן).
התנאי T1.ID<T2.ID בא להבטיח שכל קבוצה תשובץ פעם אחת נגד כל אחת אחרת, והן יופיעו על פי סדר המספרים.
מטעמי נוחות נוסיף 1 לתוצאה כדי לקבל 13 מספרי מחזור 1..13 ולא 0..12:

Select    *,

        (T1.ID+Iif(T2.ID=14,T1.ID,T2.ID))%13+1 N

From    #T T1

Inner Join #T T2

        On T1.ID<T2.ID;

image

הוסף תגובה
facebook linkedin twitter email

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *