[Python] Itertools x sport

[Daniele Varrazzo]

On 2013-01-16 11:00, Gianni wrote:
> Buongiorno, sto cercando la via più pratica per popolare il database
> di uno script per la gestione di campionati di calcio*.
>
> Dovrei associare le possibili combinazioni di partite (380) alle
> giornate (38) facendo in modo che ogni squadra giochi una sola 
> partita
> per giornata. Quindi, ho 2 liste: 20 squadre e 38 giornate.
> Le 380 partite le ottengo con permutations:
> partite = itertools.permutations(squadre, 2)
>
> Fin qui ci arrivo ma vado in palla quando cerco di associare le
> partite alle giornate.

Veramente questo mi sembra abbia un problema: non hai una distinzione 
netta tra andata e ritorno. Ovvero puoi giocare S1-S2 un giorno, poi 
S2-S1 il giorno successivo, mentre dovresti giocare S2-S1 dopo che S1 ha 
giocato con tutti gli altri. Quindi dividerei il campionato in 2 parti 
nette, andata e ritorno, e risolverei due problemi distinti: uno con

     [ p for p in itertools.permutations(range(nteams),2) if p[0] < p[1] 
]

e l'altro a squadre invertite (ma poi gestendo le coppie in maniera da 
non far giocare la prima squadra sempre in casa e via dicendo).

Un modo di fare tutto usando itertools non mi viene in mente. 
Ovviamente si tratta di un sottoinsieme di un prodotto di qualche 
insieme, ma è troppo generica come soluzione.

Ho provato un algoritmo semplice: iterare sulle partite di squadre e 
assegnare una partita ad ogni giornata dove quella partita fosse 
possibile, ovvero le due squadre non erano già impegnate: in pratica 
(esempio con 6 squadre):

     subs = []
     for p in list(itertools.permutations(range(6),2)):
         if p[0] < p[1]:
             continue
         for s in subs:
             if p[0] not in s[0] and p[1] not in s[0]:
                 s[0].add(p[0])
                 s[0].add(p[1])
                 s[1].append(p)
                 break
         else:
             subs.append((set(p),[p]))

     print [s[1] for s in subs]

Ma... non funziona. Mi aspetto che il risultato siano 5 liste di 3 
elementi ciascuna, invece è:

     [[(1, 0), (3, 2), (5, 4)],
      [(2, 0), (3, 1)],
      [(2, 1), (3, 0)],
      [(4, 0), (5, 1)],
      [(4, 1), (5, 0)],
      [(4, 2), (5, 3)],
      [(4, 3), (5, 2)]]

Il problema è che se giocano 1-0 e 3-2 il primo giorno, poi 2-0 e 3-1 
il secondo, 5-4 dovrebbero giocare due volte.

A questo punto proverei a compilare esplicitamente n-1 giornate, 
mettendo n/2 partite in ognuna, usando il backtrack ogni volta che una 
giornata è in condizione impossibile (implementato con una funzione 
ricorsiva). Ogni volta che una giornata è completata, le partite vengono 
eliminate dal pool delle partite possibili e la giornata successiva 
viene cercata in un numero ridotto di partite. Risultato:

     import itertools

     nteams = 6
     pairs = [ p for p in itertools.permutations(range(nteams),2) if 
p[0] < p[1] ]

     class Found(Exception):
         pass

     def make_matches(matches, start):
         for i, p in enumerate(pairs[start:]):
             if p[0] not in matches and p[1] not in matches:
                 nmatches = matches + p
                 if len(nmatches) == nteams:
                     raise Found(nmatches)
                 else:
                     make_matches(nmatches, i+1)

     calendar = []
     while pairs:
         try:
             make_matches((), 0)
         except Found, sol:
             sol = sol.args[0]
             matches = [ sol[i:i+2] for i in range(0, nteams, 2) ]
             calendar.append(matches)
             for p in matches:
                 pairs.remove(p)
         else:
             raise Exception('solution not found')

     import pprint
     pprint.pprint(calendar)

Questo stampa un calendario molto più verosimile.

     [[(0, 1), (2, 3), (4, 5)],
      [(0, 2), (1, 4), (3, 5)],
      [(0, 3), (1, 5), (2, 4)],
      [(0, 4), (1, 3), (2, 5)],
      [(0, 5), (1, 2), (3, 4)]]

Ovviamente l'algoritmo non si preoccupa di far sì che ogni squadra 
giochi tante volte in casa quante fuori, preferibilmente in maniera 
alternata (non so se si fa così nel campionato vero): potrebbe essere 
qualcosa che si può fare come preprocessing della lista di partite, o 
postprocessing della soluzione trovata, o potrebbe essere necessario 
modificare la ricerca per includere condizioni aggiuntive.

Penso sia anche abbastanza facile passare da una funzione che 
restituisce la prima soluzione ad un generatore che restituisce tutte le 
soluzioni possibili.

-- 
Daniele Varrazzo - Develer S.r.l.
http://www.develer.com