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
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
