Algoritmo di combinazioni molto complicato. HELP ME!!

di il
8 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

8 Risposte

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

    Presto fatto. Hai dei algoritmi già fatti e forse non lo sai.
    http://www.cplusplus.com/reference/algorithm/next_permutation/

    Tutte le combinazioni sono lì. Devi solo pescare le combinazioni giuste.
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Non è facile come credi.. provaci!
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    
    #include <iostream>
    #include <set>
    #include <algorithm>
    #include <iterator>
    
    
    int main()
    {
    	std::set<std::pair<int,int>> couples;
    	int players[] = {1,2,3,4,5,6,7,8};
    	do 
    	{
    		for(int i = 0; i < 8; i+=2)
    		{
    			couples.insert(std::make_pair(players[i],players[i+1]));
    		}
    	}while(std::next_permutation(players,players+8));
    
    	std::cout << "partite da giocare: " << couples.size() << std::endl;
    	for(std::set<std::pair<int,int>>::iterator it = couples.begin(); it != couples.end(); ++it)
    	{
    		std::cout << (it)->first << "-" << (it)->second << std::endl;
    	}
    }
    
    Te l'ho fatto x 8 giocatori, ci metteva troppo con 18. La lista di tutte le combinazioni c'è l'hai, pesca le partite giuste dal set e elimina il pair a partita trovata. considera l'attesa come un partita. con 18 giocatori hai 18*17 partite totali. scegli una partita dal set che non comprende nessuno dei giocatori già nel elenco delle partire della giornata.
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Non ci riesco ... niente!!
    poi non posso trattare le attese come un accoppiamento, perchè vanno trattati diversamente..
    un'attesa posso trovarla due volte uguale cioè 1,2 e 1,2 .. un accoppiamento no..
    le attese possono ripetersi.. gli accoppiamenti no!!
    uFF sto bestemmiando da giorni appreso a st'algoritmo ..
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Se avessi provato il mio algoritmo te ne saresti accorto che quella copia non esiste. Quindi se lo vuoi fare difficile fallo, ma non è così' dificile. Una ulteriore eliminazione (anche se non richiesta) sarebbe quella di eliminare dal set una coppia doppia e per doppia intendo <1,2> e <2,1>.
    
    #include <iostream>
    #include <set>
    #include <algorithm>
    #include <iterator>
    
    bool remove_double(std::set<std::pair<int,int>> &couples, int first, int second)
    {
    	std::pair<int,int> t(second,first);
    	if(couples.find(t) != couples.end())
    	{
    		return true;
    	}
    	return false;
    }
    
    int main()
    {
    	std::set<std::pair<int,int>> couples;
    	int players[] = {1,2,3,4,5,6,7,8};
    	do 
    	{
    		for(int i = 0; i < 8; i+=2)
    		{
    			if(!remove_double(couples,players[i],players[i+1]))
    				couples.insert(std::make_pair(players[i],players[i+1]));
    		}
    	}while(std::next_permutation(players,players+8));
    
    	std::cout << "partite da giocare: " << couples.size() << std::endl;
    	for(std::set<std::pair<int,int>>::iterator it = couples.begin(); it != couples.end(); ++it)
    	{
    		if(it->second != -1)
    			std::cout << (it)->first << "-" << (it)->second << std::endl;
    	}
    }
    
    output
    
    partite da giocare: 28 (e inteso come copie formate)
    
    1-2
    1-3
    1-4
    1-5
    1-6
    1-7
    1-8
    2-3
    2-4
    2-5
    2-6
    2-7
    2-8
    3-4
    3-5
    3-6
    3-7
    3-8
    4-5
    4-6
    4-7
    4-8
    5-6
    5-7
    5-8
    6-7
    6-8
    7-8
    
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Ecco le partite.
    
    #include <iostream>
    #include <string>
    #include <sstream>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <iterator>
    
    std::vector<int> listaTemporanea;
    
    bool remove_double(std::set<std::pair<int,int>> &couples, int first, int second)
    {
    	std::pair<int,int> t(second,first);
    	if(couples.find(t) != couples.end())
    	{
    		return true;
    	}
    	return false;
    }
    
    std::string GetNextCouple(std::set<std::pair<int,int>> &couples)
    {
    	std::set<std::pair<int,int>>::iterator it;
    	for(it = couples.begin(); it != couples.end(); ++it)
    	{
    		bool first = false, second = false;
    		std::vector<int>::iterator vecIt = std::find(listaTemporanea.begin(),listaTemporanea.end(),it->first);
    		if(vecIt == listaTemporanea.end())
    		{
    			first = true;
    			vecIt = std::find(listaTemporanea.begin(),listaTemporanea.end(),it->second);
    			if(vecIt == listaTemporanea.end())
    			{
    				second = true;
    			}
    			else continue;
    		}
    		else
    			continue;
    		if(first && second)
    		{
    			listaTemporanea.push_back(it->first);
    			listaTemporanea.push_back(it->second);
    			std::stringstream ss;
    			ss << it->first << " - " << it->second;
    			couples.erase(it);
    			return ss.str();
    		}
    	}
    	return "";
    }
    void stampa_calendario(std::set<std::pair<int,int>> &couples)
    {
    	while(!couples.empty())
    	{
    		listaTemporanea.clear();
    		std::cout << "P1 " << GetNextCouple(couples) << std::endl;
    		std::cout << "P2 " << GetNextCouple(couples) << std::endl;
    		std::cout << "P3 " << GetNextCouple(couples) << std::endl;
    		std::cout << "P4 " << GetNextCouple(couples) << std::endl << std::endl;
    	}
    }
    int main()
    {
    	std::set<std::pair<int,int>> couples;
    	int players[] = {1,2,3,4,5,6,7,8};
    	do 
    	{
    		for(int i = 0; i < 8; i+=2)
    		{
    			if(!remove_double(couples,players[i],players[i+1]))
    				couples.insert(std::make_pair(players[i],players[i+1]));
    		}
    	}while(std::next_permutation(players,players+8));
    
    	std::cout << "partite da giocare: " << couples.size() << std::endl;
    	for(std::set<std::pair<int,int>>::iterator it = couples.begin(); it != couples.end(); ++it)
    	{
    		if(it->second != -1)
    			std::cout << (it)->first << "-" << (it)->second << std::endl;
    	}
    	stampa_calendario(couples);
    }
    

    La gestione delle attese lo fai te. Devi solo creare una lista dove tieni traccia del numero di attese di ciascun giocatore.

    Output
    
    partite da giocare: 28
    1-2
    1-3
    1-4
    1-5
    1-6
    1-7
    1-8
    2-3
    2-4
    2-5
    2-6
    2-7
    2-8
    3-4
    3-5
    3-6
    3-7
    3-8
    4-5
    4-6
    4-7
    4-8
    5-6
    5-7
    5-8
    6-7
    6-8
    7-8
    
    P1 1 - 2
    P2 3 - 4
    P3 5 - 6
    P4 7 - 8
    
    P1 1 - 3
    P2 2 - 4
    P3 5 - 7
    P4 6 - 8
    
    P1 1 - 4
    P2 2 - 3
    P3 5 - 8
    P4 6 - 7
    
    P1 1 - 5
    P2 2 - 6
    P3 3 - 7
    P4 4 - 8
    
    P1 1 - 6
    P2 2 - 5
    P3 3 - 8
    P4 4 - 7
    
    P1 1 - 7
    P2 2 - 8
    P3 3 - 5
    P4 4 - 6
    
    P1 1 - 8
    P2 2 - 7
    P3 3 - 6
    P4 4 - 5
    
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Senti scusami se insisto e ripeto le stesse cose, ma temo che non hai capito bene il problema dove e quando si pone!!
    Il problema si pone dopo un certo numero di giornate..
    ad esempio se arrivati quasi alla fine una determinata giornata devono attendere i giocatori 1 2 ed io comincio a fare gli accoppiamenti ad esempio 3 8, mi posso trovare in uno stato in cui i giocatori rimanenti cioè 4 5 6 7 hanno gia giocato tutti insieme e non posso proseguire...
    Lo so che su 8 giocatori la cosa ti sembra gestibile... ma su 18 no!!!
    Ecco dove si pone il problema...
    Se io con 18 giocatori faccio come dici te, dopo un tot di giornate sono in palla!!! Perchè evidentemente ho fatto giocare giocatori insieme che poi mi serviva farli giocare insieme un'altra determinata giornata quando dovranno attendere altri due determinati giocatori...
    Il tuo algoritmo è fatto bene, ma il tuo algoritmo mi stampa solo le possibili combinazioni tra i numeri...
    Il mio problema non è quello!!!
    Io so benissimamente che ogni giocatore deve giocare insieme agli altri 17 e quindi scrivermi tranquillamente tutte le combinazioni...
    Il problema sta nel gestire il calendario con le attese dei due giocatori...
    Spero tu abbia capito il vero problema dove si pone.. e magari riesci anche ad aiutarmi...
  • Re: Algoritmo di combinazioni molto complicato. HELP ME!!

    Uppppppppppppppppp!!!
Devi accedere o registrarti per scrivere nel forum
8 risposte