[JAVA] Algoritmo per combinazioni con accoppiamenti senza ripetizioni

[fulvi00x]

Salve a tutti.
Sto cercando da tutta la notte una soluzione al mio problema, sono ormai le 7.40 e ho tanto sonno e provo a chiedere a voi..
Ho bisogno di creare un algoritmo che dati 18 numeri da 1 a 18, mi dia in output x liste. (non so quante liste posso creare, non sono riuscito ad arrivare neanche a questo risultato esatto.. cmq sono circa 34, se non 34 esatte)
Comunque ogni lista deve avere 8 coppie di numeri, che saranno i miei accoppiamenti (quindi 16 numeri da utilizzare). E 2 numeri scartati, che saranno le attese..
Il criterio da usare è questo, le attese devono essere gestite in modo equo.. cioè se nella prima lista attendono i numeri 1 2, gli stessi numeri non dovranno attendere finchè non hanno atteso tutti gli altri numeri nelle successive liste degli accoppiamenti.

Faccio un esempio pratico ora:

Lista n°1:
Attesa: 1,2
Accoppiamenti: 3,4 5,6 7,8 9,10 11,12 13,14 15,16 17,18

Lista n°2:
Attesa: 3,4
Accoppiamenti: 1,2 5,7 6,8 9,11 10,12 13,15 14,16 18,17

ecc...ecc...

Ho messo questo esempio perchè capita di avere due accoppiamenti simili (17,18 18,17) a me va bene questo basta che non siano uguali.
Insomma l'algoritmo si deve fermare di stampare liste finchè non ha più combinazioni di accoppiamenti disponibili e siano soddisfatti tutti gli accoppiamenti possibili.
Gli accoppiamenti non devono ripetersi.
Insomma devo trovarmi le 34 liste (spero il mio calcolo sia giusto) con tutti gli accoppiamenti possibili e con tutte le attese gestite in maniera ordinata.

Ho provato a scrivermi anche tutte le liste a mano.. ma arrivato alla 17esima mi sono bloccato perchè sono arrivato ad un punto in cui quando scrivevo le prime coppie di numeri che ancora non erano state utilizzate(es 1,17 2,16, 3,15 ecc), alla fine mi rimanevano coppie di numeri già utilizzate sia in un verso che nell'altro e non potevo riempire la lista bloccandomi.

Spero che qualcuno di voi sia capace di creare un algoritmo del genere, io non ci sono riuscito
E devo dire con molto dispiacere che è la prima volta da quando programmo che non riesco a risolvere un problema del genere!
Aspetto delle risposte con ansia..
Ciao a tutti.

[Cawletto]

Non capisco esattamente cosa deve fare questo algoritmo..puoi essere più chiaro? Ciao la prossima volta vai a letto prima.. A mente fresca si ragiona meglio

[fulvi00x]

mmmmh non hai capito...
Allora ti spiego in questo modo così si capisce di sicuro!
Ho 18 persone e devo organizzare un campionato di calcio balilla..
In ogni giornata del campionato 16 giocatori si scontrano in un torneo e 2 giocatori riposano..
(così da poter fare ottavi, quarti, semifinale e finale ad ogni giornata).
Quindi per ogni giornata l'algoritmo mi caccia 8 coppie di numeri e due numeri che riposano..
Le 8 coppie di numeri non sono le partite da disputare, ma semplicemente l'accoppiamento delle squadre, cioè Pippo gioca insieme a Pluto per quella giornata.. Poi gli scontri tra le squadre me la vedo io.
In pratica l'algoritmo mi deve dare il calendario delle possibili squadre da accoppiare avendo 18 giocatori diversi.. e facendo riposare 2 giocatori a giornata!
Non so come altro spiegarmi...
Fatemi sapere!!
Grazie..

[fulvi00x]

nessuno capace??

[fulvi00x]

upppp please!!!

[Davdx]

scusa ma se le persone sono 18 allora ogni persona potrà avere 17 compagni ovvero abbinamenti... ma magari sto capendo male io... potresti provare creando 17 abbinamenti di una persona e scriverli in una stringa... poi per scegliere gli abbinamenti successivi si potrebbe fare una ricerca delle occorrenze dell'abbinamento nella stringa e se ce ne fossero vorrebbe dire che l'abbinamento è già esistente, e si passa ad un altro...

[fulvi00x]

il problema è gestire le attese ...
perchè facendo come dici tu lo posso fare anche tranquillamente a mano..
Il vero problema è trovarmi dopo tutti gli accoppiamenti e aver fatto attendere esattamente x volte a tutti i giocatori.. o cmq al massimo x-1 volte a qualke giocatore.. se c'è un evidente bisogno!

Ti spiego meglio... se io arrivo ad esempio all'ultima giornata e ho da far attendere i giocatori 1 e 2 e magari faccio i primi accoppiamenti 5 8, 4 9, 11 3, mi posso trovare alla fine che tutti i giocatori che sono rimasti, hanno gia giocato insieme e non posso più proseguire negli accoppiamenti ..
è questa la cosa complicata della faccenda.. non so se riesci a seguirmi..
Perchè facendoli a caso come dici te, si arriva ad un certo punto che metti i primi accoppiamenti e gli altri non puoi + metterli perchè sono gia esistenti e non puoi proseguire...
Altro esempio, se sto creando una giornata e accoppiando tutti alla fine mi rimangono i giocatori 6 7 8 9 ancora da accoppiare, se i giocatori 6 7 8 9 hanno gia giocato tutti insieme io non posso più completare la giornata.. nonostante gli altri accoppiamenti fatti erano buoni!! ma man mano che ne rimangono di meno c'è questa impossibilità... ecco perchè voglio creare un algoritmo che mi faccia tutto!
A mano su carta e penna è praticamente impossibile...
Che storiaccia.........
Confido nella vostra mente da programmatori.....
La mia non ci arriva

[Davdx]

vedi se così ti suona meglio: crei una stringa temporanea degli accoppiamenti di giornata all'interno di un ciclo dove man mano aggiungerai i vari accoppiamenti, se un accoppiamento e' stato già effettuato nelle giornate precedenti allora azzeri la stringa temporanea e la rinizi a creare...
certo non è efficentissimo perchè verranno fatti un casino di cicli però dovrebbe funzionare...

[Andrea1979]

l'algoritmo per la generazione delle giornate di un campionato (torneo all'italiana) più usato è quello di "Berger". Trovi quintali di info se cerchi in internet "Berger tables". In pratica si tratta di costruire un array bidimensionale con 2 colonne e n/2 righe, posizionare in senso (anti)orario i partecipanti, tenere fermo un partecipante e ruotare in senso (anti)orario tutti gli altri attorno a questo pivot. Sulle righe leggerai gli accoppiamenti. Nel tuo caso puoi o scegliere che una riga (basta che non siano nè la prima nè l'ultima) sia quella dei riposi.

[fulvi00x]

ragazzi io non ci riesco....
non so come farvelo capire
non ho postato appena mi è sorto il problema!!
Ho postato dopo infinite prove...
Se qualcuno di voi è capace di fare un algoritmo del genere mi aiuti...
Potete darmi tutti i consigli teorici che volete ma se non vi mettete con codice alla mano non riuscite a capire dove sorge e quale è il vero problema!!!
Il problema non è quello di creare le combinazioni giornata per giornata.. Ma far attendere due giocatori per giornata in modo tale da arrivare alla fine delle combinazioni possibili con tutti i giocatori che hanno atteso x giornate o al massimo qualkuno che abbiamo atteso x-1 giornate.
Fatemi sapere ciauuu