Der Sieg Maschine über Mensch...

[Daen vom Clan]

... Grüße Leute, ich brauche mal ganz kurz Hilfe bei einer Sache, die mich aufgrund meiner nicht vorhandenen mathematischen Kenntnisse arg unter Druck setzt.

Und zwar geht es um die Simulation des Auslosverfahrens der Fussball-Bundesliga.

Das Problem ist, die Spielbegegnungen von 18 Mannschaften auszuknobeln.

- An jedem Tag müssen alle Mannschaften spielen
- Jede mögliche Spielpaarung darf es in dem Spielzyklus (HinRunde) nur einmal geben
- Jede Mannschaft muss mindestens einmal am Tag spielen
- Jede Mannschaft darf höchstes einmal am Tag spielen.

Wer kann mir das also auf mathematischer oder logischer Ebene erklären oder vielleicht sogar ein wahrscheinlich recht kurzes Programm entwerfen, wobei die Datensätze einfach die Zahlen 1 - 18 sein solten.

Vielen lieben Dank,
Daen

[Square]

Ich mach's mal in der Kurzversion

Hinrunde:

->Spieltag 1:
Bayern - Bremen
Dortmund - Köln

->Spieltag 2:
Köln - Bayern
Bremen - Dortmund

->Spieltag 3:
Dortmund - Bayern
Köln - Bremen

Rückrunde:

->Spieltag 4:
Bremen - Bayern
Köln - Dortmund

->Spieltag 5:
Bayern - Köln
Dortmund - Bremen

->Spieltag 6:
Bayern - Dortmund
Bremen - Köln
____________________________

So sieht das Schema aus. Es gibt 18 Teams, also gibt es pro Spieltag 9 Begegnungen. Es gibt demnach kein Team, welches spielfrei hat. Da wir 18 Teams haben, gibt es 17 Spieltage in der Hinrunde, 17 in der Rückrunde. Folglich 34 insgesamt.

Musst du einen Generator basteln? Ansonsten musst du halt aufpassen, dass du nicht die Partien doppelt nimmst. Da kannst du am besten damit anfangen, wenn du immer einzeln vorgehst. Also z.B. erst Bayern in alle Spieltage einträgst und guckst, gegen wen sie noch nicht gespielt haben. So geht das Ganze langsam auf. Ich glaub aber nicht, dir hiermit groß geholfen zu haben.

[Feenstaub]

Oh, lieber Daen!

Wir haben uns ja eine ganze Weile nicht geschrieben, gelesen, gelacht. ^^ Grüsse an deinen lieben Edelstein und die RPG-Maker-Comm.

Bzgl. deines "kleinen" Problems: Kann man zB als Komplettsuche über alle Kombinationen von 17 Spieltagen mit je 9 Paarungen machen. *grinst* Allerdings würde ich hier eher auf einen Backtrackingalgorithmus zurückgreifen. Mich würde noch interessieren, ob du es auch so haben möchtest, dass jede Mannschaft abwechselnd zu Hause bzw. auswärts spielen muss.

Ich bin gespannt auf die Lösungen von den Experten hier. Hättest' das Ganze auch als Wettbewerb laufen lassen können. Und als Preis eine Gastrolle in Sternensaga. *schon immer scharf drauf war*

Küsschen,
Feenstaub.

[Lachsen]

Hm, also mir kam nach einiger Überlegungszeit eine Idee, ich kann aber nicht garantieren, ob sie richtig ist. Sie hat sich nach einigen Tests mit 6 Mannschaften bewährt.

Eine besonders Geniale Idee ist es nicht, obs wirklich Mathematisch ist, weiß ich auch nicht.
Wenn man das ganze in einem Programm schreibt und es geschickt macht, kann es recht kurz sein.

Ich versuch nun einfach mal zu beschreiben wie das Programm vorgeht.
In dem Programm wird btw. viel mit Mengen gearbeitet, man kann zum Beispiels "Sets" verwenden um das ganze umzusetzen.

Erstmal: Es gibt 18 Mannschaften.
JEDE Mannschaft hat eine Menge namens "Gespielt". In dieser Menge wird eingespeichert, gegen welche Mannschaften diese Manschaft in der HinRunde bereits gespielt hat.

Und dann gibt es die Menge "Tag_Gespielt". In dieser Menge wird eingespeichert welche Mannschaft an diesem Tag bereits gespielt hat.

Das Programm läuft über eine doppelte Schleife... also eine Schleife in der sich eine weitere Schleife befindet.
Die erste Schleife (HinRunden-Schleife) hat für jeden Tag einen durchgang (die hat bei 18 Mannschaften genau 17 Durchgänge) Innerhalb dieser SChleife befindet sich eine zweite (Tag-Schleife), die genau für jede Paarung einmal durchläuft (also 9 mal)

--------------------------
Innerhalb der Tag-Schleife passiert nun folgendes:
1. Beginne mit der ersten Mannschaft und suche (von oben nach unten) eine Mannschaft die sich noch nicht in der Menge "Tag-Gespielt" befindet. (beim ersten durchgang der Tag-Schleife ist das immer die erste Mannschaft). Füge die gefundene Mannschaft der Menge "Tag-Gespielt" zu.

Anmerkung:
- Die gefundene Mannschaft nenne ich von nun an "Mannschaft A"
- Die "Gespielt" Menge von "Mannschaft A" nenne ich "Gespielt A"

2. Untersuche alle Mannschaften die sich nicht in der Menge "Gespielt A" und Bilde eine Rangordnung nach folgendem Kriterum:
(Untersuchte Mannschaft ist "Mannschaft B" mit der Menge "Gespielt B")

Betrachte die SCHNITTMENGE von "Gespielt B" und "Tag_Gespielt" als Zahl. Das heisst:
Gegen wieviele Mannschaften, die bereits an diesem Tag gespielt haben, hat "Mannschaft B" in der HinRunde bereits gespielt?
Bestimme die Mannschaften die nach diesemn Kriterum die NIEDRIGSTE Zahl haben. (das kann eine Mannschaft aber auch mehrere sein.). Diese Mannschaften bilden die Menge "Auswahl".

3. Wähle aus der Menge "Auswahl" zufällig eine Mannschaft. Gegen diese Manschaft wird gespielt! Füge diese Mannschaft auf der Menge "Tag_Gespielt" hinzu.

Die Tag-Schleife wiederholt sich jetzt genau 9 mal, eben bis alle Mannschaften an diesem Tag gespielt haben.
-----------------------------------
Verlässt das Programm die "Tag-Schleife", wird die "Tag_Gespielt"-Menge natürlich wieder geleert. Die "Gespielt" Mengen der einzelnen Mannschaften bleiben jedoch erhalten!

Jetzt wiederholt sich das ganze nochmal für den nächsten Tag undzwar genau 17 mal.


Also wie gesagt: Ich bin mir nicht 100%ig Sicher, ob das funktioniert, aber ich werde jetzt mal versuchen nen Java-Programm dazu zu schreiben um es zu testen XD

Ich hoffe ich konnt helfen.

Gruß

Lachsen

[Feenstaub]

@Lachsen:

Deine Idee würde in das erste Kriterium fallen: Alles komplett durchklappern! Etwas kompliziert geschrieben, aber grundsätzlich gut durchdacht. Allerdings wird es bei der Abarbeitung Probleme geben - je weiter der Algorithmus voranschreitet - weil die Möglichkeit einer Pattlösung entstehen kann.

zB. bei 6 Mannschaften:

1. Tag:
A-B
C-D
E-F

2.Tag:
A-C
D-B
???

Küsschen,
Feenstaub.

[Ineluki]

Daen .. hat Shinshrii dir die Loesung nicht schon laengst gegeben ? Ich hatte sie extra noch am selben Tag fertig gemacht -__-

Code:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

#define max 18

int main(int argc, char *argv[])
{
    vector< pair <char,char> > v,z;
    bool p[max];
    pair<char,char> m;

    for (int i=0; i<(max-1); ++i)
     for (int j=i+1; j<max; ++j)
       v.push_back(pair<char,char>(i,j));

    int day=0;
    while(!v.empty())
     {
       cout<<"Tag "<<++day<<endl;
       for (int i=0; i<max; ++i)
        p[i]=true;
       z.clear();
       for (int i=0; i<(max/2); ++i)
         for (int j=0; j<v.size(); ++j)
          {
            m = v[j];
            if (p[m.first] && p[m.second])
             {
               z.push_back(m);
               p[m.first]=false;
               p[m.second]=false;
               v.erase(v.begin()+j);
               --j;
             }
          }
       for( int i=0; i<z.size(); ++i)
        cout<<(char)(z[i].first+'A')<<"  ";
       cout<<endl;
       for( int i=0; i<z.size(); ++i)
        cout<<(char)(z[i].second+'A')<<"  ";
       cout<<endl;
     }
    system("PAUSE");
    return EXIT_SUCCESS;
}

Gruss Luki

[Feenstaub]

@Ineluki:

Wenn ich deine Lösung durch VS .NET 2003 jage, bringt er folgendes Ergebnis:

Code:

Tag 1
A  C  E  G  I  K  M  O  Q
B  D  F  H  J  L  N  P  R
Tag 2
A  B  E  F  I  J  M  N  ♫
C  D  G  H  K  L  O  P  ♫
Tag 3
A  B  E  F  I  J  M  N  ♫
D  C  H  G  L  K  P  O  ♫
Tag 4
A  B  C  D  I  J  K  L  ♫
E  F  G  H  M  N  O  P  ♫
Tag 5
A  B  C  D  I  J  K  L  ♫
F  E  H  G  N  M  P  O  ♫
Tag 6
A  B  C  D  I  J  K  L  ♫
G  H  E  F  O  P  M  N  ♫
Tag 7
A  B  C  D  I  J  K  L  ♫
H  G  F  E  P  O  N  M  ♫
Tag 8
A  B  C  D  E  F  G  H  ♫
I  J  K  L  M  N  O  P  ♫
Tag 9
A  B  C  D  E  F  G  H  ♫
J  I  L  K  N  M  P  O  ♫
Tag 10
A  B  C  D  E  F  G  H  ♫
K  L  I  J  O  P  M  N  ♫
Tag 11
A  B  C  D  E  F  G  H  ♫
L  K  J  I  P  O  N  M  ♫
Tag 12
A  B  C  D  E  F  G  H  ♫
M  N  O  P  I  J  K  L  ♫
Tag 13
A  B  C  D  E  F  G  H  ♫
N  M  P  O  J  I  L  K  ♫
Tag 14
A  B  C  D  E  F  G  H  ♫
O  P  M  N  K  L  I  J  ♫
Tag 15
A  B  C  D  E  F  G  H  ♫
P  O  N  M  L  K  J  I  ♫
Tag 16
A  B  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 17
A  B  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 18
C  D  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 19
C  D  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 20
E  F  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 21
E  F  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 22
G  H  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 23
G  H  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 24
I  J  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 25
I  J  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 26
K  L  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 27
K  L  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 28
M  N  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 29
M  N  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Tag 30
O  P  >  >  ý  ý  ý  ý  A
Q  R  >  >  ý  ý  ý  ý  A
Tag 31
O  P  >  >  ý  ý  ý  ý  A
R  Q  >  >  ý  ý  ý  ý  A
Drücken Sie eine beliebige Taste . . .

Wirkt irgendwie nicht so ganz richtig. ^^ Aber ich kann dir nicht mal sage, wieso... weil bei deinem Code sehe ich praktisch überhaupt nicht durch. Du bist entweder genial oder hochintelligent. *seufzt* Bei mir sehen Programme jedenfalls ganz anders aus. Andererseits *lächelt wieder tapfer* habe ich wahrscheinlich nicht ganz so grosse Erklärungsschwierigkeiten, wenn es um die Verdeutlichung des dahinterliegenden Algorithmus' geht. :P

Gruss,
Feenstaub.

[Ineluki]

der fehler ist korrigiert .. hatte in der ausgabeschleife (max-1) statt z.size() stehen ... was datz fuehrte, das der index des arrays ueber die grenzen gehen konnte

der algorithmus ist ganz einfach ...

In eine Liste schreibe ich alle moeglichen Kombinationen, also AB, AC, ... AR, BC, BD, BR, ..., PQ, PR, QR -> Daher die Schleife i=0, i< Max-1 und j=i+1, j< Max

mun kommt die auswertung der Tage

Ich mache eine Bitmaske mit genau so vielen stellen, wie mannschaften existieren und setze alles auf 1.

Dann nehme ich mir die erstbeste Manschaftspaarung heraus, pruefe in der bitmaske, ob kein der beteiligten Mannschaften schon gespielt hat (gespielte werden mit 0 versehen). Ist das der Fall, trage ich die Mannschaft in die Liste fuer den Tag ein und entferne sie aus dem Paarungsreservoir. Ansonsten belasse ich die Kombination unveraendert, und gehe zur naechsten. Das wiederhole ich so lange, bis ich entweder Max/2 Paarungen fuer den Tag habe, oder es keine Paarung mehr gibt, die man noch eintragen koennte fuer den Tag.

Das wird solange wiederholt, bis das Kombinationsreservoir leer ist.

[Feenstaub]

Entweder bin ich total verblödet (und müsste dann eigentlich meinen Beruf aufgeben) oder aber du bist wirklich einer von denen, die ihren Code posten, OHNE zu testen.

Code:

Tag 1
A  C  E  G  I  K  M  O  Q
B  D  F  H  J  L  N  P  R
Tag 2
A  B  E  F  I  J  M  N
C  D  G  H  K  L  O  P
Tag 3
A  B  E  F  I  J  M  N
D  C  H  G  L  K  P  O
Tag 4
A  B  C  D  I  J  K  L
E  F  G  H  M  N  O  P
Tag 5
A  B  C  D  I  J  K  L
F  E  H  G  N  M  P  O
Tag 6
A  B  C  D  I  J  K  L
G  H  E  F  O  P  M  N
Tag 7
A  B  C  D  I  J  K  L
H  G  F  E  P  O  N  M
Tag 8
A  B  C  D  E  F  G  H
I  J  K  L  M  N  O  P
Tag 9
A  B  C  D  E  F  G  H
J  I  L  K  N  M  P  O
Tag 10
A  B  C  D  E  F  G  H
K  L  I  J  O  P  M  N
Tag 11
A  B  C  D  E  F  G  H
L  K  J  I  P  O  N  M
Tag 12
A  B  C  D  E  F  G  H
M  N  O  P  I  J  K  L
Tag 13
A  B  C  D  E  F  G  H
N  M  P  O  J  I  L  K
Tag 14
A  B  C  D  E  F  G  H
O  P  M  N  K  L  I  J
Tag 15
A  B  C  D  E  F  G  H
P  O  N  M  L  K  J  I
Tag 16
A  B
Q  R
Tag 17
A  B
R  Q
Tag 18
C  D
Q  R
Tag 19
C  D
R  Q
Tag 20
E  F
Q  R
Tag 21
E  F
R  Q
Tag 22
G  H
Q  R
Tag 23
G  H
R  Q
Tag 24
I  J
Q  R
Tag 25
I  J
R  Q
Tag 26
K  L
Q  R
Tag 27
K  L
R  Q
Tag 28
M  N
Q  R
Tag 29
M  N
R  Q
Tag 30
O  P
Q  R
Tag 31
O  P
R  Q
Drücken Sie eine beliebige Taste . . .

Ich habe jetzt den Sinn hinter deinem Algorithmus verstanden, aber du hast ebenso wie Lachsen nicht an die Pattsituation gedacht, die entstehen kann (und bei dir dann auch ist).

Dadurch, dass du OHNE RÜCKWÄRTSCHRITT einfach nur die Spielpaarungen zuweist, kommt es zu Schwierigkeiten bei der Kombination.

Bestes Beispiel dafür ist bereits der zweite Tag. Dort fehlt eine Begegnung, einfach weil nur Q-R möglich wäre, diese aber schon am ersten Tag stattfand. Dabei würde einfaches Rückwärtsgehen bereits dazu führen, dass anstatt die letzten beiden Partien M-O/N-P könnten die letzten drei auch lauten: M-P/N-Q/R-O (nur als Beispiel, um zu zeigen, dass es grundsätzlich geht).

Küsschen,
Feenstaub.

[Ineluki]

Den code hab ich schon vorgestern geschrieben gehabt. Damals war das Problem fuer 16 Mannschaften gewesen ... heut hab ich den nur in einer 2 Minuten Aktion auf 18 angepasst gehabt, und gepostet, weil ich weg musste ...

bei 16 geht es zwangsweise so auf (wegen zweierpotenz) ... allerdings sehe ich am 18er beispiel auch, das da noch optimiert werden muss ...

Die frage, die sich mir allerdings stellt ist, ob es ueberhaupt moeglich ist, dass wirklich jede Mannschaft einmal am Tag spielt ...

Also Ja, dieser Code war praktisch ungetestet, und Nein, geprueft war er (mit 16) schon gewesen, und dort eine gueltige Loesung ^^

[Zudem wurden meine Vorrednerposts gar nicht gelesen, weil ich in eile war, wie bereits gesagt, uind der code schon fertig]

.. eine Anpassungsmoeglichkeit waere moeglicher Weise eine Zufallsvertauschung der ausgangskombinationen mit anschliessender ueberpruefung, solange, bis irgendwann die loesung (zwangsweise) gefunden werden muss, falls es sie gibt

[Lachsen]

@Lachsen:

Deine Idee würde in das erste Kriterium fallen: Alles komplett durchklappern! Etwas kompliziert geschrieben, aber grundsätzlich gut durchdacht. Allerdings wird es bei der Abarbeitung Probleme geben - je weiter der Algorithmus voranschreitet - weil die Möglichkeit einer Pattlösung entstehen kann.

zB. bei 6 Mannschaften:

1. Tag:
A-B
C-D
E-F

2.Tag:
A-C
D-B
???

...

Doch, ich habe das mit der Pattlösung schon durchdacht, deswegen gerade die Abfrage im Zweiten Punkt der "Tag-Schleife"...

Um es auf dein Beispiel zu beziehen:
Bei ersten Tag greift die Abfrage noch nicht, aber beim 2.:
A-C bleibt, da Tag-Menge leer ist und damit alle möglichkeuten (außer B) für A gleichwertig sind.
Tages Menge enthält nun A und C.
Nun würde das Programm mit B fortfahren.
Und wieso das Programm hier nicht D als Gegenspieler wählt:
D hat bereits mit C gespielt. C ist bereitsin der "Tag-Menge" enthalten. Dadurch bekommt die Wahl D einen Punkt.
Die Möglichkeiten E und F wiederum haben bereits Gegner gehabt (E und F), die noch NICHT in der "Tag-Menge" Menge enthalten sind. Deshalb bekommen sie keinen Punkt haben damit die niedrigste Punktzahl und damit höchste Priorität für B.

Nach diesem Prinzip kommt es zumindest in den ersten Spiel-Tagen zu keinen Fehlern...
Nur leider klappt es auch nicht so ganz :/
Am Vorletzten Spiel-Tag gibt es dann meistens nen Fehler...
Und da bin ich ehrlich gesagt am Ende von meinem Latein o_O

Immerhin hat es bei 6 Mannschaften geklappt, sofern der Zufall weg genommen wurde... Bei 16 und 18 Mannschaften wiederum nicht >_<

Schweres Thema...

C ya

Lachsen

[Ineluki]

Mein Reformierter Algorithmus hat nach 6 STunden endlich die Richtige Loesung gefunden \o/

Code:

Tag 1
B  C  A  F  D  E  I  H  G
O  N  L  R  M  Q  P  J  K
Tag 2
O  H  A  B  C  D  L  E  F
R  N  P  Q  I  G  M  K  J
Tag 3
C  I  K  A  B  G  M  D  E
H  N  O  R  F  L  P  Q  J
Tag 4
H  A  N  B  C  E  F  D  M
O  K  R  J  G  I  P  L  Q
Tag 5
H  A  O  J  B  E  D  G  K
L  C  P  N  I  R  F  M  Q
Tag 6
A  L  M  F  H  B  E  C  D
Q  R  O  N  I  K  G  P  J
Tag 7
L  G  C  A  E  D  F  B  I
O  R  Q  M  N  H  K  P  J
Tag 8
P  O  B  F  D  K  G  M  A
R  Q  C  H  I  L  J  N  E
Tag 9
D  A  M  J  G  K  F  E  C
O  B  R  Q  P  N  I  H  L
Tag 10
Q  B  F  N  A  H  C  I  D
R  G  M  P  O  K  J  L  E
Tag 11
B  I  F  J  H  N  A  K  C
L  R  G  O  P  Q  D  M  E
Tag 12
G  E  K  C  B  I  A  J  L
N  O  R  F  D  M  H  P  Q
Tag 13
J  F  G  B  A  D  C  L  E
K  Q  H  R  I  P  O  N  M
Tag 14
J  E  G  I  H  C  B  A  L
R  F  O  K  Q  D  M  N  P
Tag 15
A  F  K  B  D  H  C  J  I
G  O  P  E  N  R  M  L  Q
Tag 16
A  I  G  E  D  C  H  F  B
J  O  Q  P  R  K  M  L  N
Tag 17
A  N  P  D  E  B  G  C  J
F  O  Q  K  L  H  I  R  M

Zur ueberpruefung freigegeben ... Der Code loest aber leider bei einigen Manschaftszahlen eine Pointerexception, keine Ahnung, warum ...

Code:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

#define max 18

int main(int argc, char *argv[])
{
    srand(time(NULL));
    vector< pair <char,char> > o,v,z;
    bool p[max];
    pair<char,char> m;
    int day=0;
    int a = 0,b = 0, num=0;
    int iteration=0; 
    vector< vector< pair<char,char> > > lines;

    for (int i=0; i<(max-1); ++i)
     for (int j=i+1; j<max; ++j)
       o.push_back(pair<char,char>(i,j));
    
   while (num !=(max-1))
   {
    cout<<"\rIteration "<<++iteration<<flush;
    lines.clear(); 
    v.clear();
    v.assign(o.begin(), o.end());
    for(int i=0; i<v.size(); ++i)
     { a=(int)round((v.size()*(1.0*rand()))/RAND_MAX);
       b=(int)round((v.size()*(1.0*rand()))/RAND_MAX);
       m = v[a]; v[a] = v[b]; v[b]=m;
     }
    while(!v.empty())
     {
       for (int i=0; i<max; ++i)
        p[i]=true;
       z.clear();
       for (int i=0; i<(max/2); ++i)
         for (int j=0; j<v.size(); ++j)
          {
            m = v[j];
            if (p[m.first] && p[m.second])
             {
               z.push_back(m);
               p[m.first]=false;
               p[m.second]=false;
               v.erase(v.begin()+j);
               --j;
             }
          }
    lines.push_back(z);
     }
   num = lines.size();
    }
    cout<<endl;
    while (!lines.empty())
     { z.clear(); z.assign(lines[0].begin(), lines[0].end());
       cout<<"Tag "<<++day<<"          "<<endl;
       for(int i=0; i<z.size(); ++i)
        cout<<(char)('A'+z[i].first)<<"  ";
       cout<<endl;
       for(int i=0; i<z.size(); ++i)
        cout<<(char)('A'+z[i].second)<<"  ";
       cout<<endl;
       lines.erase(lines.begin());
     }
    system("PAUSE");
    return EXIT_SUCCESS;
}