[php] combinaties algoritme - Softwareontwikkeling

maandag 7 juni 2004 13:26

Acties:

Topicstarter

Hoi,

ik ben bezig een geautomatiseerd speelschema te ontwikkelen voor een tournooi dat wij binnenkort organiseren.

nu heb ik een array met daarin de verschillende teams.. hier zitten afhankelijk van de poule 5 of 6 spelers in.

Er moet nu een overzicht gegenereert worden van welke wedstrijden tegen elkaar gespeeld moeten worden.

wt ik kan doen is iets als

PHP:

foreach($teams,$teama){
   foreach($teams,$teamb){
       if ($teama<>$teamb){
            echo "$teama tegen $teamb";
       }
   }
}

Dan output hij dus veels teveel wedstrijden, omdat hij zowel team1 tegen team2 output als team 2 tegen team 1, maar das natuurlijk dezelfde wedstrijd.

NU zou ik dus een wedstrijd in een array kunnen zetten op het moment dat ik hem echo, en dan steeds controleren voordat ik een wedstrijd echo, of hij niet soms al in die array staat.

Toch heb ik het idee dat het makkelijker kan.
Heeft iemand een idee?

Er staat me iets bij uit de wiskunde a les van 2 boven 5 of iets dergelijks, daar mee haalt hij alle mogelijke combi's van 2 teams uit 5. waar bij 1-2 hetzelfde is als 2-1..... enkel de vertaalslag naar php, is dan nog behoorlijk pittig...

heeft iemand tips/afvies?

maandag 7 juni 2004 13:29

Acties:

gorgi_19

Kruimeltjes zijn weer op :9

[rml][ ALG] Algoritme wedstrijdschema generatie *[/rml] ?

Digitaal onderwijsmateriaal, leermateriaal voor hbo

maandag 7 juni 2004 13:32

Acties:

douweh

Topicstarter

jep die had ik al wel gevonden,

maar dat gaat dus om de uit-thuis variant, waarin iedereen 2 keer tegen elkaar speelt.

Die code heb ik zelf ook al gegeven, mijn probleem ligt dus in het feit dat ik iederen maar 1 keer tegen elkaar wil hebben spelen.

Een oplossing daarvoor heb ik ook al aangedragen, ik zou echter graag onderbouwde reacties zien voor verbeteringen, of totaal andere benaderingen.

maandag 7 juni 2004 13:35

Acties:

Janoz

Moderator Devschuur®

!litemod

Als je binnen de binnenste lus nu alleen de teams meeneemt die nig niet aan bod zijn geweest in de buitenste dan heb je die check helemaal niet meer nodig. Dat is het makkelijskte waneer je gewoon een genummerde array van teams hebt.

Dan krijg je iets als:

PHP:

$total = length($teams);
for ($i=0;$i<$total;$i++){
  for ($j=$i+1;$j<$total;$j++){
    echo $teams[$i]." tegen ".$teams[$j];
  }
}

[ Voor 6% gewijzigd door Janoz op 07-06-2004 13:40 . Reden: Al een tijdje niet meer met kleuter php gewerkt :).. Vergeet ik zo die $'s ]

Ken Thompson's famous line from V6 UNIX is equaly applicable to this post:
'You are not expected to understand this'

maandag 7 juni 2004 14:24

Acties:

douweh

Topicstarter

Janoz schreef op 07 juni 2004 @ 13:35:
Als je binnen de binnenste lus nu alleen de teams meeneemt die nig niet aan bod zijn geweest in de buitenste dan heb je die check helemaal niet meer nodig. Dat is het makkelijskte waneer je gewoon een genummerde array van teams hebt.

Dan krijg je iets als:
PHP:
1
2
3
4
5
6
$total = length($teams);
for ($i=0;$i<$total;$i++){
  for ($j=$i+1;$j<$total;$j++){
    echo $teams[$i]." tegen ".$teams[$j];
  }
}

Dit blijkt inderdaad (met enige aanpassingen) te werken! hartstikke mooi,
ik ben nu alleen aan het twijfelen of we misschien toch niet statisch de opties voor 5 en 6 teams vast moeten leggen.
Omdat je dan een mooier overzicht krijgt..

Je wil natuurlijk iets als:

code:

1-2, 3-4, 
5-6, 1-4, 
2-5, 3-6, 
1-5, 2-6, 
2-3, 4-5,
1-6, 3-5,
4-6, 1-3,
2-4

maandag 7 juni 2004 14:48

Acties:

SWfreak

Gelukkig is daar ook een mooie oplossing voor

Rotating chain algoritme oid (ben de precieze naam ff kwijt).
Idee is als volgt (voorbeeld met 11 teams)
Dag 1

code:

Dag 2

code:

en zo doordraaien....
Uitgeprogt is dit dan:

PHP:

$total = length($teams)
for( $i = 0; $i < $total; $i++ )
{     echo "Tijdstip $i";
       for( int $j = 0; $j < floor($total/2); $j++ )
            echo $teams[($total-$i+$j+$total) % $total] ." tegen " . $teams[($total-$i-$j-1+$total) % $total];
}