Sortieralgorytmus für Spieltabellen?

Einklappen
X
 
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Sortieralgorytmus für Spieltabellen?

    Hiho!
    Ich habe da ein blödes Problem. Ich möchte ein Tunier veranstalten wo sich mehrere Manschaften anmelden und gegeneinander Spielen können. Pro Tag darf ein team nur Einmal spielen. Es spielen immer jeweils 2 teams gegeneinander.
    Die Tabelle wird auch größtenteils schon wunderbar generiert, das Problem ist, dass es zu unnötigen Spieltagen kommt, wenn einige Spiele ungünstig gelegt sind.
    Bei 12 Manschaften kommt es insgesamt zu 66 Spielen. Das entspricht normalerweise 6 Spiele pro Tag. Bei meiner Tabelle "verrutschen" die Spiele zum Ende hin, so das wir schon bei 15 Tagen landen.

    Wer sehen will was ich meine: http://losclan.lo.funpic.de/Liga/ligatabellen.php

    Für Buchstaben sortieren gibt es ja Sortieralgorytmen wie Bubblesort. Gibt es sowas in der art auch für Spieltabellen? Ich glaube ich bin nicht der Erste der dieses Problem hat...

  • #2
    Zeig mal Query + Ergebnis (Daten) + gewünschtes Ergebnis...
    Für alle die Fehler suchen, gibts gratis tolle Debuggingmöglichkeiten:
    var_dump(), print_r(), debug_backtrace und echo.
    Außerdem gibt es für unsere Neueinsteiger ein hervorragendes PHP Tutorial zu PHP 4 und PHP 5 (OOP)
    Es heißt $array['index'] und nicht $array[index]! Und nein, das ist nicht egal!
    Dieses Thema lesen, um Ärger im Forum und verzögerte Hilfen zu vermeiden.

    Kommentar


    • #3
      Eins vorweg, meine Lösung ist etwas chaotisch, da ich zu blöd bin, das mit den JOINs zu kapieren, aber fang ich mal an:
      Zuerst lasse ich die Gegnerzuweisung durchlaufen. Dort wird bestimmt wer gegen wen spielen muss.
      Das ist soweit kein Problem, die Spiele passen alle.

      Nun will ich aber mit einer neuen Querry auch die Spieltage, sprich das Spieldatum festlegen. Hier der algo:

      PHP-Code:
      //Alle Spiele die Stattfinden für diese Liga auflisten
          
      $sql "SELECT SpielID, Clan1ID, Clan2ID, Datum, Ligatyp FROM $dbSpiele WHERE
                  Ligatyp = '
      {$_POST["SaisonStartID"]}'";
          
      $gamesres mysql_query ($sql);
          
      $AnzahlGames mysql_num_rows ($gamesres); //Anzahl der Spiele    

          
          //Datums eintragen
          
      for($i=0$i<$AnzahlGames$i++)
          {
                  
      //Die nächsten Zwei clans raussuchen, die gegeneinander spielen.
             
      $data mysql_fetch_array($gamesresMYSQL_ASSOC);
             
      $TempDatum $Datum//Anfangsdatum wieder setzen.
                
      do
                {
                   
      $SQLDate date("Y-n-d",mktime (0,0,0,$TempDatum["mon"],$TempDatum["mday"],$TempDatum["year"]));
                
                       
      //Hier wird gecheckt, ob einer der Beiden Mannschaften am aktuellen Datum schon spielen muss.
                   
      $sql "SELECT SpielID, Clan1ID, Clan2ID Datum, Ligatyp FROM $dbSpiele WHERE
                           (Clan1ID = '
      {$data['Clan1ID']}' OR  Clan2ID = '{$data['Clan1ID']}' OR 
                            Clan1ID = '
      {$data['Clan2ID']}' OR Clan2ID = '{$data['Clan2ID']}') 
                           AND Datum = '
      $SQLDate'";
                        
                   
      $BesetztRes mysql_query($sql);
                   
      $SpieltBereits mysql_num_rows($BesetztRes); //Wenn ja, gibts hier ein Ergebnis.
                        
                   
      if($SpieltBereits)
                   {
                      
      $TempDatum["mday"] += 7//Eine Woche weiter gehen.
                   
      }
                   else
                   {
                    
      //Ansonsten ist der Tag frei und das aktuelle Datum wird eingetragen.
                      
      $SQLDate date("Y-n-d",mktime (0,0,0,$TempDatum["mon"],$TempDatum["mday"],$TempDatum["year"]));
                      echo 
      "$SQLDate<br>";
                      
                      
      $sql "UPDATE $dbSpiele SET Datum='$SQLDate
                              WHERE SpielID = '
      {$data['SpielID']}' LIMIT 1"
                              
      mysql_query ($sql);
                   }
               }
               while(
      $SpieltBereits); //Solange wie kein freier Tag gefunden wurde,wochenweise  durchprobieren.
           

      Gewünschtes Ergebis wäre das ALLE Tabelle genauso aussehen wie bei Spieltag 1 bis 3 sprich an jedem Spieltag genau 6 Spiele. Da es keine feste Begrenzung der Spieleranzahl gibt, soll das ganze natürlich dynamisch passieren.
      Ich dachte da an eine Art sortiermethiode die nocheinmal über die Tablle drüberläuft und alle Spiele so verschiebt, das möglichst viele Spiele an einem Tag stattfinden können.

      Hier nochmal der Link zur Tabelle:
      http://losclan.lo.funpic.de/Liga/ligatabellen.php

      Kommentar


      • #4
        Informier dich bitte erstmal über SQL Injections
        Für alle die Fehler suchen, gibts gratis tolle Debuggingmöglichkeiten:
        var_dump(), print_r(), debug_backtrace und echo.
        Außerdem gibt es für unsere Neueinsteiger ein hervorragendes PHP Tutorial zu PHP 4 und PHP 5 (OOP)
        Es heißt $array['index'] und nicht $array[index]! Und nein, das ist nicht egal!
        Dieses Thema lesen, um Ärger im Forum und verzögerte Hilfen zu vermeiden.

        Kommentar


        • #5
          Mit 6 Mannschaften findet man von Hand einen Spielplan der geht, und auch Spielpläne die nicht minimal sind. Ich würde mit einem Backtracking Algorithmus die beste Lösung finden. Das heisst Du musst an diesem Tag bereits gebuchte Spiele wieder annullieren. Dazu reicht geschickte Sortierung vermutlich nicht.

          Zudem würde es nicht schaden, im Internet zu suchen, ob das überhaupt möglich ist bei einer beliebigen (geraden) Anzahl Mannschaften.

          Bei 12 Mannschaften würde ich den Backtracking Algorithmus im Arbeitsspeicher machen und nicht ständig mit DB-Abfragen, das Programm wird übersichtlicher.

          Das hat mit sql-Injection nichts zu tun, aber den $_POST solltest du schützen.

          Ubrigens deine sqldate-Zeile ruft nach einer Funktion, und die Schleife über eine Query geht nicht mit sql_num_rows und for, sondern mit while(...). Das ist Programmiertechnik.

          EDIT:
          : ich könnte mir auch vorstellen ,dass der fertige Spielplan für 12 Mannschaften schon im internet ist.
          Zuletzt geändert von phoenix20; 04.06.2006, 12:51.

          Kommentar


          • #6
            Was meinst du mit Post schützen?

            Kommentar


            • #7
              mysql_real_escape_string($_POST['spieldatum'])

              anstatt $_POST['spieldatum']

              Kommentar


              • #8
                Und wofür ist die, gegen SQL injections?

                Kommentar


                • #9
                  Original geschrieben von ThePro
                  Und wofür ist die, gegen SQL injections?
                  ja

                  Ein netter Guide zum übersichtlichen Schreiben von PHP/MySQL-Code!

                  bei Klammersetzung bevorzuge ich jedoch die JavaCoding-Standards
                  Wie man Fragen richtig stellt

                  Kommentar


                  • #10
                    Wie weit bist Du mit dem Backtracking gediehen, bzw. dem fertige Spielplan aus dem Internet?

                    Kommentar


                    • #11
                      bis jetzt bin ich noch nicht weitergekommen. Ich denke mal, das ich die komplette zuweisungsroutine nocheinmal überdenken muss.
                      Das Ganze ist ziemlich kompliziert. Notfalls lege ich die Mitspieleranzahl auf 12 Spieler fest.
                      So müsste ich nur noch von hand auf einem Blatt schauen, wie es sein müsste damit alles passt und das ganze einfach Hardcoden.
                      Ist zwar ne beschissene löseung, aber ich denke anders bekomme ich es wohl nicht hin.

                      Kommentar


                      • #12
                        hier das fast fertige programm:

                        PHP-Code:
                        <?php
                         fopen
                        ("http://www.sbbl.org/web/paarungstabelle.htm");

                        echo 

                        Paarungstabelle für  Spieler/Mannschaften


                        --------------------------------------------------------------------------------
                        Rd 1 2 3 4 5 6 
                        1  1 - 12  2 - 11  3 - 10  4 -  9  5 -  8  6 -  7 
                        2 12 -  7  8 -  6  9 -  5 10 -  4 11 -  3  1 -  2 
                        3  2 - 12  3 -  1  4 - 11  5 - 10  6 -  9  7 -  8 
                        4 12 -  8  9 -  7 10 -  6 11 -  5  1 -  4  2 -  3 
                        5  3 - 12  4 -  2  5 -  1  6 - 11  7 - 10  8 -  9 
                        6 12 -  9 10 -  8 11 -  7  1 -  6  2 -  5  3 -  4 
                        7  4 - 12  5 -  3  6 -  2  7 -  1  8 - 11  9 - 10 
                        8 12 - 10 11 -  9  1 -  8  2 -  7  3 -  6  4 -  5 
                        9  5 - 12  6 -  4  7 -  3  8 -  2  9 -  1 10 - 11 
                        10 12 - 11  1 - 10  2 -  9  3 -  8  4 -  7  5 -  6 
                        11  6 - 12  7 -  5  8 -  4  9 -  3 10 -  2 11 -  1 
                        '
                        ;

                        echo 
                        'tschüss';
                         

                        ?>

                        Kommentar


                        • #13
                          PS auch sourcecode kannst Du dir selber holen wenn Du weisst wie (nicht bei mir). Dann hast Du den algorithmus.

                          es gibt sogar viele Lösungen, das heisst jede Permutation der Nummern ist auch ein Spielplan.

                          edit:
                          http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=54015

                          (Seite 4!)
                          http://www.google.ch/search?q=spielplan+12+mannschaften+jeder+gegen+jeden&hl=de&lr=&newwindow=1&start=30&sa=N
                          Zuletzt geändert von phoenix20; 05.06.2006, 01:38.

                          Kommentar


                          • #14
                            DANKE! Ich wusste wie. Hast mich aber auf dumme Gedanken gebracht du schlimmer Finger.

                            So sieht das Ganze in PHP aus:
                            http://losclan.lo.funpic.de/Liga/Test.php

                            Sieht genauso aus wie die Java Tabelle bei 12 Mannschaften. Der Rest dürfte kein Problem sein. Ich melde mich nochmal, wenn ich es geschafft habe.

                            Kommentar


                            • #15
                              VIELEN VIELEN DANK @ phoenix20!!!!
                              Ich war mit diesem Problem Tagelang beschäftigt und kurz davor gewesen alles hinzuschmeißen.
                              Jetzt funktioniert alles so wie es soll, auch wenn ich es auf eine etwas unmoralische Art gelöst habe.

                              http://losclan.lo.funpic.de/Liga2/ligatabellen.php

                              DANKE DANKE DANKE!!!
                              ICH LIEBE DIESES FORUM!

                              Kommentar

                              Lädt...
                              X