Algoritmo della parentesi del torneo

3

Sto cercando algoritmi per creare parentesi ad eliminazione singola e doppia eliminazione.

Il primo passo era capire l'algoritmo di seeding, incluso bye, che ho trovato in diversi punti in SO: qui (dove i byte possono essere introdotti semplicemente b sostituendo gli ultimi n team in eccesso e spostando le posizioni seme n volte) e qui (ciao sono cotti dentro, e ho solo bisogno di spostare le posizioni).

Che è un miglioramento rispetto all'algoritmo che stavo usando quali squadre abbinate come questa: [(x, -x - 1) for x in range(num_players / 2)] e invece di definire il prossimo round come ci si aspetterebbe: Winner Match_i vs Winner Match_i+1 sarebbe Winner Match_i vs Winner Match_n-i , abbastanza non intuitivo e più difficile da mantenere .

Ma ora sto cercando di definire gli algoritmi per creare le parentesi. Ho difficoltà a trovare algoritmi effettivi per generare parentesi di eliminazione singole e doppie parentesi di eliminazione.

Non sono troppo preoccupato per la generazione di parentesi ad eliminazione singola perché è piuttosto semplice, anche con i byte e anche considerando che sto supportando diverse modalità di consolazione.

Ma le parentesi a doppia eliminazione mi stanno buttando fuori. Ovunque guardi, vengono costruiti in un modo diverso. E non è solo che non posso sceglierne uno, è anche che non riesco a capire come creare le associazioni tra le partite, specialmente quando sono coinvolti i bye perché rompono la struttura delle parentesi e rendono il problema più difficile da risolvere.

Vorrei pubblicare il mio codice ma è piuttosto lungo, disordinato e ha alcuni bug in cui la staffa non viene generata correttamente, ecco perché sto cercando altri affidabili algoritmi di generazione di parentesi.

    
posta dabadaba 30.06.2017 - 11:10
fonte

1 risposta

2

Poiché ti offre il codice e che ti indicano una risorsa sono entrambi fuori tema cercherò di mostrarti come rendere molto più facile scrivere la propria soluzione a questo problema.

Invece di farti girare la testa sulle soluzioni pubblicate per il problema di programmazione, consulta un esperto di dominio:

There are two ways to run single or double elimination tournaments --- either "Blind Draw" or "Seeded".

Seeded Tournaments are usually run with a league or season event so that skill level can be determined.

The number one ranked team players the lowest ranked seed, the number two ranked team plays the second lowest ranked seed and so on.

You will need to estimate the number of teams to determine if you want a Single or Double elimination tournament. After this has been determined, follow the rules of Single or Double elimination tournaments.

erasabletournamentbrackets.com - Seeded Tournaments

Ciò significa che per farlo diventare teste di serie, dobbiamo mettere le squadre in ordine di classifica prima che inizi il torneo tra parentesi. Se li lasciamo piazzati casualmente, è cieco. Sembra che tutto ciò che dobbiamo fare sia aggiungere una fase di ordinamento quando si esegue il seeding. Dopodiché dovremmo essere in grado di utilizzare lo stesso codice sia per i seeded che per i blind.

Confrontaattentamentequestidueevedraicheineffettifunzionanoinmodomoltosimile.Ladifferenzaèl'ordine.1gioca16èunbuonmodopercostruirelepartiteperchétuttoquellochedevifareèclassificarleinordineepoiabbinareilmeglioconilpeggio.Questomodellomiglioreepeggioresiripetementreandiamodaunroundall'altro.Questoassicuracheseilvincitoreèsempreilpiùaltoinclassifica,allora1nonha2perilpiùalungopossibile.Dovrebbeesserepossibilegeneralizzarequestoperqualsiasipotenzadi2.

Tuttopuòesseregestitoordinandoivincitoridell'ultimoroundinbaseallorogradopre-torneoefacendodinuovotutto.Faianchequestoperiperdentiehaiilturnosuccessivodellatoperdentedelladoppiaeliminazione.

Finiscituttoavendoilvincitoredeivincitoridifrontealvincitoredeiperdenti.

Quindidiciamochepuoifaretuttociòchefunziona.Chediredi ciao ?

bye 1 |bī| noun 1 the transfer of a competitor directly to the next round of a competition in the absence of an assigned opponent.

[From the New Oxford American Dictionary.]

Per simulare un torneo con bye avrei raggiunto il mio schema preferito. Il modello di oggetto nullo può farti lasciare tutto il codice precedente da solo creando semplicemente un concorrente nullo che rappresenta l'assenza di un oggetto assegnato avversario. Come? Loro perdono sempre. In questo modo puoi avere parentesi che NON iniziano con una potenza di 2. Come dire 12:

Osservalo attentamente e potresti notare ciò che ha in comune con il campo seminato di 16 giocatori. Tutto è lo stesso tranne che alcuni punti sono stati cancellati. Quelle macchie cancellate sono dove mettere i giocatori di oggetti nulli che perdono sempre.

Per fare in modo che funzioni per la stampa semplicemente sopprimerai la stampa di una parentesi che contiene un oggetto oggetto nullo.

Ciò significa che sei libero di fare le tue azioni nel primo round o in qualsiasi round senza cambiare il tuo codice semplicemente introducendo giocatori che perdono sempre e non stampano la loro parentesi.

Con questi bytes dovrebbe essere possibile generalizzare questo per qualsiasi numero di concorrenti.

    
risposta data 01.07.2017 - 16:27
fonte

Leggi altre domande sui tag