Newsgroup: it.comp.lang.c
Titolo: campionato

Ciao a tutti, sto cercando di fare un programma per giocare al
fantacalcio...
non riesco però a fare un algoritmo che generi il campionato, mi spiego
meglio:
date n squadre voglio generare le (n-1) giornate in modo che ogni squadra
giochi con tutte le altre.
non vi chiedo di scrivermi il codice, ma di darmi almeno qualche spunto
concettuale per la realizzazione dell'algoritmo.
Grazie in anticipo a tutti
Gnagno

 concettuale per la realizzazione dell'algoritmo.
Se mi dici a quali di questi due sei interessato posso aiutarti
ulteriormente!
Tommy

 scontato che sia cosi'!
Anche io aborro il calcio (in realta' l'idea di agonismo in quanto
tale....)
pero' la cosa mi sembra fattibile:
Date n squadre ci sono giustamente n*(n-1)/2 coppie.
Pero', se la frase "andata  e ritorno" ha un qualche significato,
allora presumo che in un campionato vogliano fare tutte
le partite 2 volte per il discorso di giocare in casa e fuori.
Quindi abbiamo n*(n-1) partite.
Supponendo che n sia pari e che ogni volta giochino tutte le
squadre, allora possiamo fare ogni volta n/2 partite
e quindi in n*(n-1)/(n/2) = 2(n-1) "giornate"
dovremmo cavarcela.
(Siccome tu parli di n-1 giornate mi viene il
sospetto che nel fantacalcio, qualunque cosa esso sia,
non si facciano andata e ritorno.)
Quindi direi che il difficile nel generare un calendario
consiste non nel generare le n*(n-1) coppie, ma nel
ficcare le n*(n-1) partite in 2(n-1) giornate,
con l'ovvio vincolo che nella stessa giornata non possa
giocare 2 volte la stessa squadra.
Poi presumo che (nel campionato reale) il calendario
sia in realta' ottenuto imponendo maggiori
vincoli, del tipo che le piu' forti non
si scontrano direttamente all'inizio o che una squadra
non gioca fuori casa 5 volte di seguito.
Bisognerebbe sapere quali e quanti vincoli ci
sono nel tuo "fantacalcio".
Questo perche' direi che il problema (e l'algoritmo da usare)
dipende piu' che altro dai vari vincoli che vengono
imposti (e che io non conosco).
Posso solo immaginare che con qualche libreria di
ottimizzazione si possa ottenere il tutto facilmente
in qualche ora di lavoro e sarei curioso di sapere quanti miliardi di 
lire abbiano invece probabilmente spillato quelli
che fanno queste cose per il campionato "vero".
ciao,
g.

Ringrazio sia Tommy che Giovanni, effettivamente sono stato molto poco
preciso nello spiegare il mio problema.
Lo vado a spiegare meglio, ipotizziamo di avere n squadre,
ogni squadra deve giocare nel corso di tutto il campionato con tutte le
altre (n-1) squadre.
una giornata è composta da n/2 partite fra coppie di squadre, nelle n/2
partite di ogni giornata sono distribuite tutte le n squadre, quindi una
squadra gioca una partita per ogni giornata e in una giornata giocano tutte
le squadre.
Inoltre nel corso del campionato due squadre si possono incontrare una ed
una sola volta (non importa quale delle due sia in casa tanto poi per
costruire il girone di ritorno inverto casa e trasferta).
Ecco, il problema consiste appunto nel generare le giornate, faccio un
esempio, ipotizziamo di avere 4 squadre A, B, C e D un possibile risultato
potrebbe essere:
Giornata 1:
A - B
C - D
Giornata 2
C - A
B - D
Giornata 3
A - D
B - C
avevo n=4 squadre, ci sono n-1 giornate e in ogni giornata n/2 incontri.
Grazie a chiunque altro si voglia cimentare in questo problema

Ecco qui, spero non fosse un compito da fare a casa, perche'
per principio non voglio fare compiti altrui...
Comunque non non e' detto che sia la soluzione migliore.
Anzi, sicuramente ci sara' un algoritmo specifico e deterministico
ma non avevo voglia/tempo per pensarci.
Questo programmino buttato giu' di getto,
genera velocemente calendari per numeri
di squadre pari e dispari fino a circa una trentina.
Sostanzialmente genero casualmente l'ordine nel
quale tentero' di inserire una data partita nelle
varie giornate e poi cerco di inserire in quel
modo, usando un po' di backtracking in caso di fallimento.
Se la ricorsione prende
troppo tempo allora probabilmente ho scelto un ordinamento
iniziale cattivo e ricomincio. Questo sistema funziona quando
ci sono molte soluzioni al problema che vogliamo risolvere ma
anche alcuni vicoli ciechi.
Per favore non guardare alla pulizia stilistica ma solo
al metodo. Ci ho messo 15 minuti a fare il programma e
il doppio a mettere i commenti...
ciao,
g.
// ===== giorn.c =======
// uso:  giorn NS   dove NS e' il numero (pari o dispari) di squadre
// ==================
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/* queste sono le funzioni per numeri casuali
(seme e generazione) che uso sulla mia
macchina, caso mai cambiale */
#define MYRANDSEED(x) srand48(x)
#define MYRAND()  lrand48()
/* numero massimo di squadre */
#define MX 40
int nS; /* numero squadre */
int nP;   /* numero partite */
int nG;   /* numero giornate */
int nPxG; /* numero partite per giornata */
/* inG[g] numero di partite gia' allocate nella giornata  g*/
int inG[MX];
/* SinG[g][s] vale 1 se ho gia' allocato una partita
    della squadra s nella giornata g */
unsigned char SinG[MX][MX];
/* Cal[g][0..nPxG-1] sono le partite allocate nella giornata g */
int Cal[MX][MX/2];
/* una partita e' data da una coppia di interi che
    identificano le 2 squadre */
typedef struct { int a,b;} Partita;
/* Part[i].a=S1, Part[i].b=S2 indica che la partita i-esima
    coinvolge le squadre S1 e S2 */
Partita Part[MX*MX/2];
/* LookOrd[p][0..nG-1] contiene i numeri da 0 a nG-1 in ordine
casuale, per ogni partita p. In pratica LookOrd[p] indica
la sequenza delle giornate nelle quali cerchero' di allocare
la partita p.*/
int LookOrd[MX*MX/2][MX];
/* questa funzione prende un vettore di interi v, lungo
n e permuta casualmente i suoi elementi */
void randvec(int *v, int n)
{ int i,r,sw;
   for (i=0; i<n; i++)
     {
       r = (MYRAND()>>10)% (i+1);
       sw = v[r]; v[r]=v[i]; v[i]=sw;
     }
}
//contatore globale del numero di chiamate ricorsive
// serve per interrompere una ricerca troppo lunga
int rcal=0;
// cerca di allocare la partita p in qualche giornata
// (e ricorsivamente tutte le partite maggiori di p)
int GenCal(int p)
{
   int ig,candg,ris,tmpinG;
   // se ho fatto piu' di 500mila chiamate alla funzione GenCal,
   // allora ritorno un fallimento (2) in modo da ricominciare
   // da capo da una altro punto.
   if (++rcal>500000) return 2;
   // se ho esaurito tutte le partite allora ho trovato una
   // soluzione e lo segnalo ritornando 1.
   if (p==nP) return 1;
   //  provo a mettere la partita p nelle varie giornate
   for (ig=0; ig<nG; ig++)
     {
       // giornata candidata = candg
       candg=LookOrd[p][ig];
       // memorizzo in tmpinG quante partite ho gia' nella
       // giornata candg,
       // perche' mi serve in caso di soluzione per memorizzare
       // la partita relativamente alla giornata
       tmpinG = inG[candg];
       // se nella giornata candg ci sono gia' nPxG partite,
       // non posso usarla e la salto
       if (tmpinG>=nPxG) continue;
       // se nella giornata cand giocano gia' le squadre della
       // partita p allora non va bene
       if (SinG[candg][Part[p].a] || SinG[candg][Part[p].b]) continue;
       // ok. Se arrivo qui allora la giornata candg puo'
       // andare bene. La inserisco, aggiornando inG e SinG
       inG[candg]++;
       SinG[candg][Part[p].a]=SinG[candg][Part[p].b]=1;
       // invoco la procedura ricorsiva sulla prossima partita
       ris=GenCal(p+1);
       // se ho un risultato diverso da 0 so che comunque la
       // procedura deve terminare. Mi segno l'accoppiamento
       // partita-giornata, nel caso tutto vada bene.
       if (ris) {Cal[candg][tmpinG]=p; return ris;}
       // rimetto le cose a posto prima di provare la
       // prossima candidata
       inG[candg]--;
       SinG[candg][Part[p].a]=SinG[candg][Part[p].b]=0;
     }
   // se arrivo qui ho esaurito i miei candidati, e ritorno 0
   // per segnalare il fallimento.
   return 0;
}
// bisogna passare come primo parametro il numero di
// squadre
int main(int argc, char *argv[])
{
   int g,p,s,ip,s1,s2;
   // indica se il numero originario di squadre era dispari
   // in quel caso l'ultima squadra e' finta
   int DispFlag=0;
   if (argc<2)
   {printf("devi indicare il numero di squadre\n"); return 0;}
   nS = atoi(argv[1]); // squadre
   if (nS<2||nS>MX){printf("Squadre tra 2 e %d\n",MX); return 0;}
   // se nS e' dispari lo aumento di 1 e mi ricordo
   // questo fatto
   if (nS&1) {nS++; DispFlag=1;}
   nP = nS*(nS-1)/2; // partite
   nG = nS-1;        // giornate
   nPxG = nS/2;     // partite per giornata
   //inizializzo il generatore di numeri casuali
   MYRANDSEED(time(0));
   // ripeto fino a che non trovo una soluzione
do
   {
   printf("--- Provo\n");
   // azzero il contatore di chiamate ricorsive
   rcal=0;
   // determino casualmente l'ordine (delle giornate)
   // in cui cerchero' di ficcare una partita
   for (p=0; p<nP; p++)
     {
       for (g=0; g<nG; g++) LookOrd[p][g]=g;
       randvec(LookOrd[p],nG);
     }
   // nessuna partita ancora allocata a nessuna giornata
   for (g=0; g<nG; g++) inG[g]=0;
   // numero le partite da 0 a nP-1 e mi segno per ogni
   // partita le 2 squadre coinvolte
   for (p=s1=0; s1<nS; s1++)
     for (s2=s1+1; s2<nS; s2++) {Part[p].a=s1; Part[p++].b=s2;}
// azzero i flag che mi dicono quali
// squadre stanno gia' giocando
// in una data giornata
   for (g=0; g<nG; g++)
      for (s=0; s<nS; s++) SinG[g][s]=0;
   }
// ripeto fino a che non ottengo successo
   while (1!=GenCal(0));
// stampo la soluzione
// se il DispFlag e' a 1 e se una squadra gioca
// con l'ultima squadra (finta), allora assumo che si
// debba riposare
  printf("\n");
   for (g=0; g<nG; g++)
     {
       printf("--- GIORNATA  %2d ----\n",g+1);
       for (ip=0; ip<nPxG; ip++)
	{
           p=Cal[g][ip];	
	  if (DispFlag==0 || Part[p].b<nS-1)
           printf("%2d <-> %2d\n",
                   1+Part[p].a, 1+Part[p].b);
           else printf("%2d riposa\n",1+Part[p].a);
	}
       printf("---------------------\n");
     }
   return 0;
}
//================================================================
// ciao,g.

 g.
Accidenti, grazie mille non dovevi disturbarti tanto, non è un compito per
casa ma una cosa amatoriale.
Cmq chiedevo soltanto che mi si desse qualche spunto, al massimo qualche
dritta in pseudocodice, non il codice per la generazione del tutto, mi hai
levato la parte più divertente, vabbè allora vorrà dire che mi leggerò il
tuo e me lo rifarò da capo per conto mio usando il metodo che hai usato tu
(non perchè non ritenga valido il tuo codice sia chiaro, ma perchè
altrimenti non imparo niente se copio e incollo qui e la).
Grazie ancora per l'aiuto
Gnagno