[LØST] Algoritme for oppsett av terminliste

[Kimble]

Jeg holder på med et script som skal sette opp en terminliste for et gitt antall lag (f.eks. 10). Alle lagene skal spille hver runde og i løpet av sesongen skal alle lagene ha spilt en kamp mot alle, altså ingen hjemme og bortekamp. Ingen lag skal heller spille to kamper en runde.

 

Slik jeg har begynt å gjøre det nå har jeg en liste over alle lag og en liste over mulige motstandere for hvert lag. Etterhvert som jeg setter opp kamper stryker jeg de lagene som mulige motstandere for hverandre samt at jeg fører de opp på en liste over lag som allerede har spilt den runden slik at ingen lag blir satt opp på to kamper samme runde.

 

Problemet er at jeg ikke får det til å gå opp!! (her skulle det egentlig vært en smily som river av det siste håret sitt)..

 

Det virker som om rekkefølgen man går gjennom lagene på er avgjørende og det klarer jeg ikke å lage en algoritme for.

 

Her er resultatet mitt så langt:

Kjørende script: http://www.bprog.no/algoritme.php

Kildekode: http://www.bprog.no/algoritme.phps

 

.phps fila er bare en symbolsk lenke fra php fila og er derfor alltid oppdatert. Håper virkelig noen kan hjelpe meg med dette mens jeg enda har hår igjen på toppen :-) Jeg trenger sansynligvis ikke noe hjelp med koden, det er algoritmen som er vanskelig!

Endret 12. august 2007 av astrox

[Kimble]

Hm.. lurer på om det ikke er et matteproblem som har bitt meg i ræva

 

La oss si at vi har 10 lag. Da kan dette visualiseres som et halv sjakkbrett (delt på diagonalen). Med 10 lag skal det være 5 kamper per runde for at det skal gå opp. Løsningen på problemet blir da alle måter 5 tårn kan plasseres på sjakkbrettet uten å true hverandre.

 

Spørsmålet er om det er noe system i løsningene som kan utnyttes for å generere terminliste for et tilfeldig (par) antall lag?

[Kimble]

http://www.bprog.no/algoritme.php

 

Som dere ser der kan ikke lag 5 og 6 spille mot hverandre i runde 2 fordi de allerede har møtt hverandre i den første runden. Hadde de møtt andre lag i runde 1 hadde det gått bra (iallfall den runden).

 

Problemet er at når man velger lag til kampene i en runde vet man ikke om det vil skape problemer senere.

 

Hoff.. det nærmeste jeg har vært en løsning har involvert "kvalifisert" gjetting på tilfeldige tall og brute force For hver runde har jeg vedlikeholdt et array for hvert lag over mulige motstandere. Der det har vært flere å velge mellom har jeg valgt en tilfeldig motstander. Da har jeg kunnet kjøre den funksjonen flere ganger til den tilfeldigvis har kommet opp med en løsning, men det er ikke en brukbar løsning for sesonger med flere enn 12 lag.

 

En annen løsning hadde vært å systematisk gå gjennom alle mulighetene, men det blir igjen veldig programmeringsteknisk og etterhvert og når antall lag stiger blir det ekstremt mange løsninger som skal testes.

 

Finnes det virkelig ingen lur algoritme som garanterer løsning på et forsøk?

[Kimble]

Dæven! Der fikk jeg det til!

 

Var nok en lur algoritme ja.. Om noen skulle trenge det samme en gang er det Round Robin som brukes til dette. Her er noen nyttige lenker:

 

http://en.wikipedia.org/wiki/Round-robin_t...uling_algorithm

http://www.devenezia.com/downloads/round-robin/ - Med bra visualisering av problemet

http://www.bprog.no/RoundRobinTournament.phps Kildekoden min etter at jeg fikk det til.

 

Denne forumtråden ble jammen monolog fra min side

[kikkazz]

Dæven! Der fikk jeg det til!

 

Var nok en lur algoritme ja.. Om noen skulle trenge det samme en gang er det Round Robin som brukes til dette. Her er noen nyttige lenker:

 

http://en.wikipedia.org/wiki/Round-robin_t...uling_algorithm

http://www.devenezia.com/downloads/round-robin/ - Med bra visualisering av problemet

http://www.bprog.no/RoundRobinTournament.phps Kildekoden min etter at jeg fikk det til.

 

Denne forumtråden ble jammen monolog fra min side

9263108[/snapback]

 

Har slitt med det samme før så dette var et bra tilskudd

 

Men jeg har enda et lite problem som jeg ikke klarte å finne ut av.

Det er hvis antall lag er oddetall?

Prøvde å lese gjennom de linkene du limte inn her, meeen skjønte stort sett ingen ting av det som sto der.

 

Hadde vært fint om du kunne ha hjulpet meg?

[Runar0]

Vist du har for eksempel 5 lag så legger du til eit 'dummy' lag som nummer seks og det laget som blir parret med lag seks slipper og spille den runda.

[Kimble]

Var digg å få det til Sleit med det hele forbanna dagen i går. Den sjakkideen førte ikke frem for å løse problement, men det er kanskje en tøff måte å vise hvem som skal matche hverandre hver runde..

Endret 12. august 2007 av astrox