Generazione di calendari

Messaggioda mela82 » 01/03/2013, 00:20

Ciao chi di voi non ha mai organizzato un torneo sia esso di calcio, Fantacalcio o di qualsiasi altro gioco o sport in cui ė previsto che i partecipanti si scontrino in coppie????

Da qualche giorno mi sto mangiando la testa con un quesito di questo tipo:

Supponiamo di avere 8 partecipanti e di voler creare un calendario degli incontri in cui ciascun partecipante sfida una volta sola tutti gli avversari... In altre parole stiamo parlando di un calendario di calcio di sola andata in cui in ciascuna delle 7 giornate si svolgono 4 partite.

La mia domanda ė quanti possibili calendari DISTINTI esistono considerando 8 partecipanti
Dove per distinti intendo sia la possibilità che uno stesso incontro avvenga in una delle 7 diverse giornate (A-B prima giornata oppure seconda o terza...) sia che possano cambiare due soli abbinamenti di una stessa giornata esempio:

Prima giornata
A-B
C-D
E-F
G-H

Oppure
A-B
C-D
e-h
f-g

Spero di essere stato chiaro
mela82
Starting Member
Starting Member
 
Messaggio: 1 di 3
Iscritto il: 28/02/2013, 23:27

Re: Generazione di calendari

Messaggioda Obidream » 01/03/2013, 04:27

Anche se non ti so rispondere con precisione forse questo esempio può aiutarti:

Supponiamo che un 'urna contenga $n>=2$ palline di colore diverso.
Chiediamoci: in quanti modi possiamo estrarre le palline dall'urna ? Quando estraiamo la prima
pallina, effettuiamo una scelta tra le $n$ palline presenti nell 'urna ; poi estraiamo la seconda pallina, scegliendola tra le $n-1$ palline rimanenti; la terza è scelta tra le $n-2$ palline rimanenti , e così via. In totale, abbiamo dunque:
$n(n- 1) ·. . .·2·1 = n!$

risultati diversi dell'estrazione delle palline: $n!$ rappresenta il numero di possibili disposizioni di $n$ oggetti distinti in sequenza , oppure il numero di possibili permutazioni di $n$ oggetti ordinati.
Se ci limitiamo a $k$ estrazioni, con $0 < k < n$ ; abbiamo :
$n(n - 1) . . . (n - k + 1)n!$ risultati possibili. Tale espressione, che puo essere scritta come:

$(n!)/((n-k)!)$

rappresenta il numero di possibili disposizioni di $n$ oggetti distinti in sequenze
di k .
((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000))
Avatar utente
Obidream
Senior Member
Senior Member
 
Messaggio: 772 di 1065
Iscritto il: 07/02/2012, 21:57

Re: Generazione di calendari

Messaggioda superpippone » 01/03/2013, 15:29

Per il momento posso solo dirti che come prima giornata hai $105$ combinazioni diverse.
La quarta ne ha $24$.
La sesta $4$.
La settima (ovviamente) $1$.
Per il resto ci penserò.
Comunque siamo nell'ordine di milioni!!
Avatar utente
superpippone
Senior Member
Senior Member
 
Messaggio: 207 di 1925
Iscritto il: 03/02/2011, 15:20
Località: TRIESTE

Re: Generazione di calendari

Messaggioda mela82 » 01/03/2013, 20:55

Obidream ha scritto:Anche se non ti so rispondere con precisione forse questo esempio può aiutarti:

Supponiamo che un 'urna contenga $n>=2$ palline di colore diverso.
Chiediamoci: in quanti modi possiamo estrarre le palline dall'urna ? Quando estraiamo la prima
pallina, effettuiamo una scelta tra le $n$ palline presenti nell 'urna ; poi estraiamo la seconda pallina, scegliendola tra le $n-1$ palline rimanenti; la terza è scelta tra le $n-2$ palline rimanenti , e così via. In totale, abbiamo dunque:
$n(n- 1) ·. . .·2·1 = n!


Condivido quanto dici... Però se consideriamo che n in questo caso rappresenti le 7 giornate potrei generare 7! (Chiamo questo numero A) calendari ma direi che non sono tutti in quanto gli abbinamenti nelle giornate non sono cambiati...

Se considero la singola giornata dovrei avere $ (n!)/(k!(n-k)!) $ (chiamo questa formula B) possibili abbinamenti
dove n=8 rappresenta il numero di partecipanti e k=2 il numero di posti (cioè l'accoppiamento a due a due delle otto squadre)

Probabilmente potrei considerare A*B come estremo superiore di tutti i possibili calendari distinti che di potrebbero avere... Che ne dite?


superpippone ha scritto:Per il momento posso solo dirti che come prima giornata hai $ 105 $ combinazioni diverse.
La quarta ne ha $ 24 $.
La sesta $ 4 $.
La settima (ovviamente) $ 1 $.
Per il resto ci penserò.
Comunque siamo nell'ordine di milioni!!



Probabilmente hai ragione, ma dovresti essere più chiaro spiegando da dove escono fuori quei numeri altrimenti non capisco...

Comunque grazie a tutti del vostro aiuto
mela82
Starting Member
Starting Member
 
Messaggio: 2 di 3
Iscritto il: 28/02/2013, 23:27

Re: Generazione di calendari

Messaggioda superpippone » 04/03/2013, 10:03

Ciao.
Ci ho pensato e provato molto nel week-end.
Ho alcune certezze e molti problemi.
Le certezze sono:
1° giornata $105$ (calcolate);
2° giornata $60$ (contate);
3° giornata $32$ (contate);
4° giornata $15$ (contate).
Fin qui siamo a $105*60*32*15=3.024.000$.
Poi cominciano i problemi: a seconda di cosa si sceglie alla 4° giornata, alla 5° avrò da 5 a 10 opzioni.
Alla sesta ne avrò da 2 a 4 (forse anche 5).
Alla settima sempre 1.
Per fare un calcolo esatto bisognerebbe sviluppare TUTTE le "quindicine" possibili. Ovvero $32*15=480$.
E poi fare tutte le 5° e 6° giornate possibili.
E per me, che uso carta e penna, è impossibile.
Mi dispiace, ma "getto la spugna".
Avatar utente
superpippone
Senior Member
Senior Member
 
Messaggio: 208 di 1925
Iscritto il: 03/02/2011, 15:20
Località: TRIESTE

Re: Generazione di calendari

Messaggioda mela82 » 07/03/2013, 20:34

superpippone ha scritto:Ciao.
Ci ho pensato e provato molto nel week-end.
Ho alcune certezze e molti problemi.
Le certezze sono:
1° giornata $ 105 $ (calcolate);
2° giornata $ 60 $ (contate);
3° giornata $ 32 $ (contate);
4° giornata $ 15 $ (contate).
Fin qui siamo a $ 105*60*32*15=3.024.000 $.
Poi cominciano i problemi: a seconda di cosa si sceglie alla 4° giornata, alla 5° avrò da 5 a 10 opzioni.
Alla sesta ne avrò da 2 a 4 (forse anche 5).
Alla settima sempre 1.
Per fare un calcolo esatto bisognerebbe sviluppare TUTTE le "quindicine" possibili. Ovvero $ 32*15=480 $.
E poi fare tutte le 5° e 6° giornate possibili.
E per me, che uso carta e penna, è impossibile.
Mi dispiace, ma "getto la spugna".


Scusami ma sono stato un po' occupato negli ultimi giorni.
Continuo a non capire come le hai calcolate o contate... potresti fare un esempio pratico
Grazie per il tempo che hai dedicato...
mela82
Starting Member
Starting Member
 
Messaggio: 3 di 3
Iscritto il: 28/02/2013, 23:27

Re: Generazione di calendari

Messaggioda Stewe86 » 12/04/2017, 18:10

Ciao, se qualcuno fosse ancora interessato all'argomento in questione, penso di aver risolto il problema del calcolo del numero possibile di calendari. Indicando con $n$ il numero di squadre e considerando anche il fattore campo (cioè si considera differente giocare in casa o in trasferta) si ha che il numero possibile di calendari differenti $C$ è dato dalla seguente formula:

$ C=( ((n!)/(2^(n/2)*(n/2)!)), (n-1) )*2^((n-1)*n/2)*(n-1)! $

Nel caso non si volesse tenere in considerazione il fattore campo, è sufficiente eliminare il secondo fattore della formula, che quindi diventa:

$ C=( ((n!)/(2^(n/2)*(n/2)!)), (n-1) )*(n-1)! $

Per fare un esempio, nel caso di $8$ squadre si avrebbe un numero possible di calendari dell'ordine delle centinaia di migliaia di miliardi senza considerare il fattore campo (per la precisione $C=114714047448000$).
Nel caso qualcuno volesse sapere i passaggi effettuati per arrivare e queste formule o avesse bisogno di qualche chiarimento me lo faccia sapere.
Stewe86
Starting Member
Starting Member
 
Messaggio: 1 di 1
Iscritto il: 12/04/2017, 17:23

Re: Generazione di calendari

Messaggioda massimopiacere » 09/05/2018, 17:40

Ciao a tutti. Nel caso di 8 squadre, ho calcolato tutte le possibili permutazioni che risultano della combinazione degli 8 elementi, ovvero 40320 righe di 56 elementi

Li ho poi ridotti eliminando le ripetizioni ottenendo 1680 combinazioni di 56 elementi

Le 1680 combinazioni le ho date in pasto all'algoritmo di Berger , e di fatto ho ottenuto 1680 diversi calendari , con la corretta alternanza casa - fuori .

Per quanto mi risulta, alla domanda , " QUANTI POSSIBILI CALENDARI POSSONO ESSERE CREATI A 8 SQUADRE ? " , la risposta è 1680

Saluti
massimopiacere
Starting Member
Starting Member
 
Messaggio: 1 di 1
Iscritto il: 09/05/2018, 17:25

Re: Generazione di calendari

Messaggioda Algorithm9 » 29/12/2018, 15:39

Stewe86 ha scritto:Ciao, se qualcuno fosse ancora interessato all'argomento in questione, penso di aver risolto il problema del calcolo del numero possibile di calendari. Indicando con $n$ il numero di squadre e considerando anche il fattore campo (cioè si considera differente giocare in casa o in trasferta) si ha che il numero possibile di calendari differenti $C$ è dato dalla seguente formula:

$ C=( ((n!)/(2^(n/2)*(n/2)!)), (n-1) )*2^((n-1)*n/2)*(n-1)! $

Nel caso non si volesse tenere in considerazione il fattore campo, è sufficiente eliminare il secondo fattore della formula, che quindi diventa:

$ C=( ((n!)/(2^(n/2)*(n/2)!)), (n-1) )*(n-1)! $

Per fare un esempio, nel caso di $8$ squadre si avrebbe un numero possible di calendari dell'ordine delle centinaia di migliaia di miliardi senza considerare il fattore campo (per la precisione $C=114714047448000$).
Nel caso qualcuno volesse sapere i passaggi effettuati per arrivare e queste formule o avesse bisogno di qualche chiarimento me lo faccia sapere.



Ciao, mi sto scontrando con lo stesso problema (ma con un girone a 6 squadre). Ho provato ad effettuare dei calcoli (non me ne intendo di calcolo combinatorio, quindi sono al 99% sbagliati), e ottengo che con 6 squadre è possibile generare 960 calendari distinti. I criteri per determinare se un calendario è distinto da un altro sono:
  • Non è significativo chi gioca in casa e in trasferta (quindi uno scontro AvsB è uguale a uno scontro BvsA).
  • Non conta l'ordine delle partite in una giornata (perciò una giornata AvsB, CvsD, EvsF è uguale alla giornata CvsD, BvsA, FvsE).

Per questo motivo sarei interessato a conoscere i passaggi che hai effettuato per arrivare alla formula, perchè vorrei capire dove sbaglio nel calcolo che porta il mio risultato ad essere cosi diverso dal tuo.

Ho anche provato a creare un programma che crei tutti i possibili calendari, ma ne ottengo solo 720 (sempre con 6 squadre).

Grazie!
Ciao
Algorithm9
Starting Member
Starting Member
 
Messaggio: 3 di 3
Iscritto il: 03/04/2018, 21:10

Re: Generazione di calendari

Messaggioda superpippone » 31/12/2018, 12:05

Confermo.
Con un girone a 6 squadre, i calendari possibili sono $720$.
Più precisamente hai le seguenti opzioni:
1° giornata $15$
2° giornata $8$
3° giornata $3$
4° giornata $2$
5° giornata $1$

e $15*8*3*2*1=720$
Avatar utente
superpippone
Senior Member
Senior Member
 
Messaggio: 1869 di 1925
Iscritto il: 03/02/2011, 15:20
Località: TRIESTE

Prossimo

Torna a Pensare un po' di più

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti