Algoritmo di combinazioni molto complicato. HELP ME!!!

di il
7 risposte

Algoritmo di combinazioni molto complicato. HELP ME!!!

Salve a tutti, dopo tanti anni di sviluppo mi ritrovo in un forse banale problema..
Vi spiego la mia situazione..
Ho 18 giocatori singoli, devo creare un campionato di calcio balilla a coppie.. Quindi i giocatori non giokeranno mai singolarmente...
Ora vi spiego prima la parte teorica .. Insomma la traccia ihihih
Vorrei che in ogni giornata 16 giocatori siano impegnati e due giocatori riposano..
Dei 16 giocatori impegnati si andranno a formare 8 coppie..
Il metodo in cui si scontreranno le coppie non è un problema ora, me la vedo io..(faccio un torneo ad eliminazione ogni giornata).
Il problema fondamentale è gestire le attese dei 2 giocatori che rimangono fermi ad ogni giornata.. e gestire a dovere le coppie di giocatori.. insomma un giocatore non deve giocare 3 volte con un altro giocatore e magari nessuna volta con un altro giocatore.. dovrà giocare due volte con l'uno e due volte con l'altro .. o almeno la cosa dovrà essere più equa possibile..
Secondo i miei calcoli arrivati a 34 giornate ogni giocatore avrà giocato due volte con ogni altro giocatore.. quindi ad esempio la coppia 1,2 e 2,1 è possibile vederla in due giornate diverse.. visto che il giocatore 1 può giocare due volte con il giocatore 2 e viceversa...
Ovviamente le coppie identike non vanno bene tipo la coppia 1,2 non potremo mai vederla più di una volta!!!
Altra cosa da puntualizzare è la gestione delle attese.. ad esempio se la prima giornata attendono i giocatori 1,2 ; gli stessi giocatori 1,2 non dovranno attendere se prima tutti gli altri giocatori non hanno fatto un turno di attesa..
Questo è quello che voglio creare..
Parlando di programmazione... ho provato con cicli while annidati, for infiniti ecc ecc NULLA!!
Non sono riuscito a creare un algoritmo che mi faccia queste combinazioni..
In poche parole l'algoritmo, dati in input 18 numeri interi da 1 a 18, mi dia in output x liste.
Ogni lista è costituita da 8 coppie di numeri mai ripetuti.. e due numeri di attesa che dovranno essere gestiti in modo equo..
Ovviamente tutte le coppie che vengono gia assegnate in una lista non devo comparire mai + nelle liste successive.. questo tenendo conto dell'ordine dei numeri.. cioè [ coppia 1,2 == coppia 1,2 ] ma [ coppia 1,2 != coppia 2,1 ] .
Spero di essere stato kiaro..
Per quanto riguarda i due numeri di attesa, non fa niente se capita che due giocatori attendano due volte insieme .. cioè se la prima giornata attendono 1,2 dopo 9 giornate non ho problemi a far attendere di nuovo 1,2 insieme!!!
Ragazzi help me!!
Fino a qlk giorno fa credevo di essere un buon programmatore...
Mi sono dovuto ricredere
Spero qualcuno sia capace di aiutarmi...
A presto

7 Risposte

  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Ciao, premesso che il tuo problema non è banale, io cercherei su google qualcosa sulle tabelle di Berger o ricerca direttamente l'algoritmo di Berger.
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Ci ho gia provato.. ma senza risultati soddisfacenti
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Ciao se io dovessi risolvereil tuo problema farei così, mi prendo la tabella di berger riferita a 18 giocatori poi sostituisco i giocatori 17 e 18 con il giocatore fittizio "riposo" , dopodichè associo ogni nome reale di squadra ad un numero e sostituisco .Le squadre che incontrano il giocatere " riposo" .. ..riposeranno

    Se non vuoi farlo carta e penna la sostituzione ti rocca scivere un programmino che data in input la tabella di berger e una lista di squadre, sostituisca e stampi un calendario.( problema molto pià semplice di quello tuo di partenza)

    Se la tua è invece è una sifda a trovare l'algoritmo che faccia gli abbinamenti fai come ha fatto
    Johann Berger cioè scervellati e buona fortuna
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Non è possibile fare come pensi te ...
    ti spiego il motivo!!
    se come dici tu faccio riposare i giocatori 17 e 18 riposeranno sempre gli stessi giocatori cioè i giocatori associati al numero 17 e al numero 18 =)
    poi non ho capito bene, dici di far riposare i giocatori che giocano con i giocatori 17 e 18 ma facendo così, cioè facendo riposare quei due devo per forza far giocare insieme i giocatori 17 e 18
    e ad ogni partita giocheranno insieme
    in pratica... mi serve a poco l'output dell'algoritmo di berger.. quell'algoritmo mi da in output semplicemente tutte le possibili combinazioni di due numeri tra i 18 numeri!!
    se tra quelle combinazioni scelgo a caso due giocatori "riposo" non risolvo il problema se era così semplice già avevo risolto ehhehe
    non so, mi sa che questo campionato non si farà è una cosa troppo complicata!!!
    io credevo di essere io ad avere dei limiti, invece ho capito che l'algoritmo è davvero complicato!!
    datemi una manoooo
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Ciao l'idea mia di sfruttare le tabelle di berger, ma che non è applicabile al caso tuo poichè tu vuoi far riposare due giocatori , era questa:
    
    public class CreaCalendario {
    
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            // TODO code application logic here
        String [] team={"","Roma","Milan","Juventus","Inter","Lazio","Riposo"};// il primo elemento è necessario nullo
        // tabella di berger riferita a 6 giocatori (1 giocatore riposa) 
        // vettore casa contiene i numeri di squadra che giocano in casa presi riga per riga letti da sinistra a destra
    // vettore fuiori contiene i numeri di squadra che giocano fuori casa presi riga per riga letti da sinistra a destra
    
    
        int [] casa={1,2,3,6,5,1,2,3,4,6,1,2,3,4,5};
        int  [] fuori={6,5,4,4,3,2,6,1,5,5,4,3,6,2,1};
        int indicegiornate=1;
    
            for (int i = 0; i < casa.length; i++) {
          
         if(i==0 )System.out.println((indicegiornate++)+"° Giornata");
                  // if(casa[i]!=6 && fuori[i]!=6)//se commento if,  stamapa pure squadra che riposa
                                System.out.println(team[casa[i]]+" - "+team[fuori[i]]);
                
                    if((i+1)%((team.length-1)/2)==0 && i!=casa.length-1)
                    {
                        System.out.println(" ");
                        System.out.println((indicegiornate++)+"° Giornata");
                   }
            }
    
        }
    
    }
    
    
    


    il cui output è il seguente:
    1° Giornata
    Roma - Riposo
    Milan - Lazio
    Juventus - Inter

    2° Giornata
    Riposo - Inter
    Lazio - Juventus
    Roma - Milan

    3° Giornata
    Milan - Riposo
    Juventus - Roma
    Inter - Lazio

    4° Giornata
    Riposo - Lazio
    Roma - Inter
    Milan - Juventus

    5° Giornata
    Juventus - Riposo
    Inter - Milan
    Lazio - Roma

    In questo caso ci sono 5 giocatori e ad ogni turno ne riposa uno. Se ne ripsassero 2 di giocatori , la giornata in cui si scontrano roposo1 vs riposo2 comprometterebbe tutto il calendario.
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Io sono arrivato ad una soluzione abbastanza efficiente..
    ma nel migliore dei casi mi si blocca all'ultima giornata.. (ho provato a fare solo un giro di scontri, cioè che ognuno gioca una sola volta con tutti gli altri!!)
    l'ultima giornata non riesce mai a riempirla facendo in modo che tutti i giocatori hanno giocato con tutti gli altri 17 almeno una volta
    posto il codice, magari prendete degli spunti e riusciamo a risolvere..
    il codice è sporco, ho fatto tante prove quindi non mi ci metto a commentare e a badare alle piccolezze.. ma compila ed esegue tranquillamente!!
    fatemi sapere
    CLASSE GIOCATORE
    package calendario;
    import java.util.*;
    
    public class Giocatore {
    	public String nome;
    	public int id;
    	public int numPartGiocate;
    	public int numAttese;
    	List<Integer> listaCompagni;
    	
    	public Giocatore(int id){
    		this.nome="scon";
    		this.id=id;
    		this.numPartGiocate=0;
    		this.numAttese=0;
    		this.listaCompagni = new ArrayList<Integer>();			
    	}
    
    	public String getNome() {
    		return nome;
    	}
    
    	public void setNome(String nome) {
    		this.nome = nome;
    	}
    
    	public int getId() {
    		return id;
    	}
    
    	public void setId(int id) {
    		this.id = id;
    	}
    
    	public int getNumPartGiocate() {
    		return numPartGiocate;
    	}
    	
    	public void incrNumPartGiocate(){
    		numPartGiocate = numPartGiocate + 1;
    	}
    
    	public void setNumPartGiocate(int numPartGiocate) {
    		this.numPartGiocate = numPartGiocate;
    	}
    
    	public int getNumAttese() {
    		return numAttese;
    	}
    
    	public void setNumAttese(int numAttese) {
    		this.numAttese = numAttese;
    	}
    
    	public List<Integer> getListaCompagni() {
    		return listaCompagni;
    	}
    
    	public void setListaCompagni(List<Integer> listaCompagni) {
    		this.listaCompagni = listaCompagni;
    	}
    }
    MAIN
    package calendario;
    import java.util.*;
    public class Main {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Giocatore[] giocatori;
    		Giocatore x;
    		int giornata = 1;
    		int index=0,casuale;
    		int partecipanti = 18;
    		giocatori = new Giocatore[partecipanti];
    		List<Integer> giornataTemp;
    		giornataTemp = new ArrayList<Integer>();
    		int i;
    		for (i=0; i<18; i++){
    			x = new Giocatore(i);
    			giocatori[i] = x;
    		}
    		while(true){
    			giornataTemp.clear();
    			System.out.printf("Giornata %2d !\n", giornata);
    			giornata = giornata +1;
    			int j=0;
    			while (j<16){
    			for (i=0; i<18; i++){
    				if (giocatori[i].getNumPartGiocate() <= giocatori[index].getNumPartGiocate() )
    					if (!giornataTemp.contains(giocatori[i].getId()))
    						index = giocatori[i].getId();
    			}
    			giocatori[index].incrNumPartGiocate();
    			giornataTemp.add(index);
    			System.out.printf("ID: %2d   PartiteGiocate: %d      &      ", giocatori[index].getId(), giocatori[index].getNumPartGiocate() );
    			casuale = generaRandom(index, giornataTemp, giocatori[index].getListaCompagni());
    			giocatori[casuale].incrNumPartGiocate();
    			giornataTemp.add(casuale);
    			giocatori[index].listaCompagni.add(casuale);	
    			giocatori[casuale].listaCompagni.add(index);
    			System.out.printf("ID: %2d   PartiteGiocate: %d \n", giocatori[casuale].getId(), giocatori[casuale].getNumPartGiocate());
    			j=j+2;
    			}
    		}
    	}
    	
    	static int generaRandom(int ind, List<Integer> giornataT, List<Integer> listaC){
    		int xyz;
    		while(true){
    		xyz = (int) Math.floor(Math.random()*18);
    		if ((xyz != ind) && !giornataT.contains(xyz) && !listaC.contains(xyz) )
    			return xyz;
    		}
    	}
    
    }
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!!

    Upppppppppppppppp!!!
Devi accedere o registrarti per scrivere nel forum
7 risposte