Spielplan

[Struppi]

Ich hoffe Heute ist es auch möglich echte Probleme zu lösen.

Ich suche einen Algorithmus um einen Spielplan zu erstellen. Also ich habe eine x-beliebige Anzahl von Teilnehmern oder Teams und die sollen alle gegeneinander antreten.

Der Ansatz in Perl:

  
sub spielplan  
{  
    my $teams = shift;  
    die "$teams ist kein Array" unless ref $teams eq 'ARRAY';  
    my $anzahl_teams = scalar @$teams;  
    if($anzahl_teams % 2)  
    {  
        push @$teams , 'Spielfrei';  
        $anzahl_teams++;  
    }  
    my $anzahl_spiele =  ($anzahl_teams -1) * $anzahl_teams / 2;  
    my $tage = $anzahl_spiele / int($anzahl_teams / 2);  
    print "$anzahl_teams:$anzahl_spiele:$tage\n";  
  
    my %tage;  
    my @spiele;  
    my $count = 1; # nur zur Kontrolle  
    $anzahl_teams--; # wg. Index = 0  
    for my $i1 (0..$anzahl_teams )  
    {  
         for my $i2 (0..$anzahl_teams )  
         {  
              next if ( $i1 == $i2) or ($i2 > $i1);  
              print "$count.$i1-$i2\n";  
              push @spiele, [$i1, $i2];  
              $count++;  
         }  
    }  
    return;  
}

Jetzt hab ich in dem Array Spiele alle Paarungen (der Hinrunde).

Wie kann ich jetzt rausfinden, welche Spieltage möglich sind?

Es ist wohl irgendeine Art der Rekursion wobei jedes Spiel miteinander kombiniert werden muss und die Kombinationen, die die Anzahl der Paarungen pro Spieltag ergeben sind mögliche Spieltage.

Aber ich komm einfach nicht dahinter wie ich diese Programmieren muss.

Struppi.

[Struppi]

Aber ich komm einfach nicht dahinter wie ich diese Programmieren muss.

Also, es ist wohl dieses "Händler auf Reisen"-Problem.
Also ein Baum auf dem ich alle Möglichkeiten durchlaufe und bei einer Abbruchbedingung den nächsten Zweig probieren muss. Ich hab sowas noch nie gemacht. Kann man das kurz erklären oder nach was muss ich suchen?

Was mir nicht klar ist, wie durchlaufe ich einen Baum und finde den letzten gültigen Zweig?

Struppi.

[Mathias Bigge]

Hi Struppi,

meinst Du sowas wie eine Paarungstabelle? Im Schachbereich wird da viel Freeware angeboten und sicher gibt es auch irgendwo den entsprechenden Algorithmus.

Viele Grüße
Mathias Bigge

[Struppi]

meinst Du sowas wie eine Paarungstabelle? Im Schachbereich wird da viel Freeware angeboten und sicher gibt es auch irgendwo den entsprechenden Algorithmus.

Danke, noch ein Suchbegriff.

Werd mich am Montag mal hinsetzen.

aber das ganze scheint nicht so trivial zu sein, alles was ich gefunden hatte (das travelling salesman Problem) war derart akademisch (ich hab noch nicht mal Abitur) das mir das nicht weiterhilft, da ich die meisten Mathematischen Formeln nicht mehr lesen kann.

Ich werd wohl versuchen müssen das auf meine Weise zu lösen.

Struppi.