Newsgroup: it.comp.www.php
Titolo: Combinazioni per partite torneo

Supponiamo di avere 10 o 12 squadre che partecipano ad un torneo.
La formula del torneo è semplice: in un giorno si gioca tutti contro tutti a seguire
 
So che le partite saranno n(n-1)/2 dove n=num.squadre
 
Ho una pagina ins.php che è un semplice form dove definisco i nomi delle squadre. Passerei i valori alla pagina che calcola le combinazioni.
 
Il mio obiettivo sarebbe quello di non far mai giocare ad una squadra due partite consecutive.
 
Come potrei fare?

 Come potrei fare?
 
Studiare qualche algoritmo
 
M.

 Studiare qualche algoritmo
 
Quale?


L'algoritmo della non consecutivitá di due partite della stessa squadra.
 
-- 
g4b0, linux user n. 369000
http://brosulo.net
 

 Quale?
 
 
Algoritmi di abbinamento e (opzionalmente) ordinamento dati.
 
Ad essere sinceri ogni organizzazione ha delle regole precise negli
abbinamenti, espressi in maniera piů o meno dettagliata e algoritmica.
 
Per esempio negli scacchi la FIDE ha scritto un manuale come effettuare
gli abbinamenti, con la descrizione di un vero e proprio algoritmo: i
programmatori prendono il manualone e a manella implementano l'algoritmo
nel loro linguaggio preferito...
 
M.

 M.
 
 
Fa nulla ... grazie lo stesso ...


Molto interessante.
Personalmente appena posso ci perdo un po' tempo...
Ovviamente non è sempre possibile, come nel caso banale di N==3 o N==4, ma non riesco a prima vista a generalizzare quando questo lo sia o meno.
Implementare un brute-force è ovviamente banale (e se vuoi una soluzione veloce forse ti conviene, trovando in seguito la soluzione elegante solo per curiosità): fai una lista di incontri, un'array delle permutazioni da 1 a N, e scorri la lista ordinata secondo quest'ultimo finché non trovi una o più configurazioni possibli. Nel caso di poche squadre te le cavi con poco ;)
M2C, e se riesco a inventare qualcosa vi aggiorno! :)
Ciao!

 
 
Ci sono guide o siti o gente che ne ha parlato sui forum?
Non riesco a capire come fare... 
 
Sembra che chiedo segreti di stato ... nessuno sa nulla ... le risposte sono tutte sfuggenti :(
 
Forse devo separare le cose e chiederne una alla volta? ...ma in tal caso sarei ancora in difficoltà perchè non facile scomporre il problema

 Forse devo separare le cose e chiederne una alla volta? ...ma in tal caso sarei ancora in difficoltà perchè non facile scomporre il problema
 
si tratta di matematica combinatoria
leonardo


sorry, permutazioni da 1 a N(N-1)/2, ovviamente! ;)
P.S. Fossi in te a non trovare risposte gireri la domanda anche su i.c.p o i.s.m! Ciao!

fai una lista di incontri, un'array delle permutazioni da 1 a N, e scorri la lista ordinata secondo quest'ultimo finché non trovi una o più configurazioni possibli. Nel caso di poche squadre te le cavi con poco ;)
 
ecco ... come potrei approfondire questa procedura? Tu la definisci semplice... io no...
Metto le squadre in array e poi mi fermo lì :(((
Cosa intendi per 2permutazioni da 1 a N?

 Cosa intendi per 2permutazioni da 1 a N?
 
In realtà l'ho fatta un po' troppo facile, ma il concetto era il seguente (e scrivendolo ho capito che è inapplicabile):
Se hai 6 squadre (1,2,3,4,5,6) hai 15 incontri (1-2,1-3,1-4,1-5,1-6,2-3,etc.etc.), per cui (senza il vincolo da te posto) 15! possibili sequenze di incontri, che sono un bel po' (e qui sta il problema). Per ogni permutazione dei numeri da 1 a 15 vedi se la detta permutazione (intesa come array degli indici del vettore degli incontri) genera una lista che ha i requisiti necessari.
Il problema con questo approccio è che con 10 squadre se ti dice male dovresti calcolare 45! possibili liste, che direi non essere viabile :)
 
Sempre nel caso di 6 squadre, in realtà, se tieni conto del vincolo e se inizi con, mettiamo, 1-2, ci sono 7 incontri non possibili (dove giocano 1 e 2), e ne rimangono quindi 7. Per ognuno di questi sette provi quello che viene dopo, considerando che adesso in realtà ci sono solo 6 incontri possibili (uno si è già disputato!). E si prosegue così fino ad esaurimento ;)
 
Detto questo mi sono permesso di girare la domanda anche su i.s.m, vediamo cosa mi dicono ;)
Ciao!

 Come potrei fare?
 
Ho dato un'occhiata in giro e questo algoritmo potrebbe essere un buon 
punto di partenza, magari si puo' modificare per fare in modo che nel 
primo accoppiamento di ogni giornata non ci sia una squadra che era 
nell'ultimo della precedente, ma sarebbe da studiare.
 
Appena riesco gli do un'occhiata anche io, potrebbe servirmi per un 
torneo di luglio :P
 
Ciao
-- 
MMM

 Come potrei fare?
 
dimenticato il link :P
it.wikipedia.org/wiki/Algoritmo_di_Berger
 
 
Ciao
-- 
MMM

 
 
Nel frattempo l'avevo trovato anch'io... Però mi sembra che non soddisfi a pieno le esigenze di un torneo che inizia la mattina e finisce la sera.
Infatti questo separa le partite in giornate (e come dicevi anche tu.. senza guardare chi gioca l'ultima della giornata precedente), poi non gestisce tornei di squadre dispari, e infine fa controlli (in questi casi inutili) su chi gioca in casa e chi fuori casa...

On Friday, June 1, 2012 3:06:41 PM UTC+2, rics wrote:

Ok, ho chiesto su it.scienza.matematica, qui il thread
http://groups.google.com/group/it.scienza.matematica/browse_thread/thread/f5b3e649495f6a11/4496b08065e2ee7b
 
A quanto risulta dalla penultima risposta (di frengo) sembra semplice: il perché funzioni non lo so, ma tant'è :)
Trasformare il tutto in un algoritmo PHP è a questo punto banale!
Ciao!

 Ok, ho chiesto su it.scienza.matematica, 
 
Non mi è chiara la condizione "tale che ogni concorrente non faccia due 
incontri consecutivi", mi sembra che gli incontri siano tutti 
consecutivi, cioè non ci sia mai un turno di riposo.


Per come l'ho capita io, c'è solo un "campo", quindi gli incontri non sono in contemporanea ma consecutivi.
Ciao!

 Per come l'ho capita io, c'è solo un "campo", quindi gli incontri non sono in contemporanea ma consecutivi.
 
 
Esatto, si gioca in un solo campo, dalla mattina alla sera. Se ho 6 squadre si devono giocare 15 partite "una dietro l'altra".
Vorrei evitare che la stessa squadra faccia 2 (o più) incontri consecutivi...
Questo sarebbe fisicamente "provante" per la squadra A
A vs B
A vs C
A vs D
... 
 
Mentre sarebbe meglio distribuire la fatica alternando gli incontri, come ad esempio
A vs B
C vs D
E vs F
A vs C
.....
 
 
 

 Trasformare il tutto in un algoritmo PHP è a questo punto banale!
 
 
Molto interessante, grazie mille