WM-Vorrunde: Wieviele verschiedene Punktkombinationen?

Neue Frage »

ck0815 Auf diesen Beitrag antworten »
WM-Vorrunde: Wieviele verschiedene Punktkombinationen?
Hallo allesamt!

Zuerst vorweg: ich bin (leider) keine besondere Leuchte in Mathematik und versuche nun schon seit geraumer Zeit, ein Problem zu lösen, das mit der Fußballweltmeisterschaft zu tun hat.

Das Ziel ist, die Zahl aller möglichen Punktkombinationen in der Vorrunde zu ermitteln, bzw. die unmöglichen Kombinationen zu finden und dabei eben keine zu übersehen. Leider komme ich selbst nicht über die "Vorrunde" hinaus, habe bis jetzt lediglich festgestellt, dass am Ende der Vorrunde keine Mannschaft 8 Punkte haben kann - das ist nun nicht besonders schwer. Und dass es am Ende des ersten Spieltags (bei 4 Teams mit Drei-Punkte-Regelung) von den Bestandteilen her nur drei mögliche Kombinationen gibt: 3 3 0 0; 3 1 1 0 und 1 1 1 1.

Und dann geht's los: Mir ist nicht klar, ob es wichtig ist, dass es ja auch 3 0 3 0, 3 0 0 3 und noch andere Permutationen gibt (ich denke aber das es wichtig ist) und wie man dann die folgenden Spieltage und Möglichkeiten am besten überschauen kann.

Wie fängt man das denn am besten an?

Viele Grüße
C.
HAL 9000 Auf diesen Beitrag antworten »

Tja, diese Frage liegt wohl gerade in der Luft (warum wohl Big Laugh ) - mir wurde sie vorige Woche von einem Kollegen gestellt. Da habe ich sie einfach mal per Bruteforce mit einem kleinen Progrämmchen beantwortet. Es sind folgende 40 möglichen Tabellenausgänge (nur Punkte, kein Torverhältnis):

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
   9   6   3   0  :  -111/2-11/22-1/222-
   9   6   1   1  :  -111/2-11/22-0/220-
   9   4   4   0  :  -111/2-01/20-1/222-
   9   4   3   1  :  -111/2-10/22-1/202-
   9   4   2   1  :  -111/2-01/20-0/220-
   9   3   3   3  :  -111/2-12/22-1/212-
   9   2   2   2  :  -111/2-00/20-0/200-
   7   7   3   0  :  -011/0-11/22-1/222-
   7   7   1   1  :  -011/0-11/22-0/220-
   7   6   4   0  :  -101/2-11/02-1/222-
   7   6   3   1  :  -110/2-11/22-1/022-
   7   6   2   1  :  -101/2-11/02-0/220-
   7   5   4   0  :  -011/0-01/20-1/222-
   7   5   3   1  :  -011/0-10/22-1/202-
   7   5   2   1  :  -011/0-01/20-0/220-
   7   4   4   1  :  -110/2-01/20-1/022-
   7   4   3   3  :  -011/0-12/22-1/212-
   7   4   3   2  :  -110/2-10/22-1/002-
   7   4   3   1  :  -101/2-01/00-0/220-
   7   4   2   2  :  -101/2-10/02-0/200-
   7   3   2   2  :  -011/0-00/20-0/200-
   6   6   6   0  :  -211/1-21/21-1/222-
   6   6   4   1  :  -211/1-21/21-0/220-
   6   6   3   3  :  -121/2-11/12-2/221-
   6   5   4   1  :  -211/1-00/20-1/202-
   6   5   2   2  :  -211/1-00/20-0/200-
   6   4   4   3  :  -112/2-01/20-1/122-
   6   4   4   2  :  -211/1-20/21-0/200-
   5   5   5   0  :  -001/0-01/00-1/222-
   5   5   4   1  :  -001/0-10/02-1/202-
   5   5   3   2  :  -010/0-10/22-1/002-
   5   5   3   1  :  -001/0-01/00-0/220-
   5   5   2   2  :  -010/0-01/20-0/020-
   5   4   4   3  :  -001/0-12/02-1/212-
   5   4   4   2  :  -100/2-10/02-1/002-
   5   4   3   2  :  -100/2-01/00-0/020-
   5   3   3   2  :  -001/0-00/00-0/200-
   4   4   4   4  :  -210/1-02/20-1/012-
   4   4   4   3  :  -120/2-10/12-0/000-
   3   3   3   3  :  -000/0-00/00-0/000-

(Die hinteren Zahlen kennzeichnen für jedes Punktequadrupel ein exemplarisches Ergebnistableau mit (wie üblich) 1=Sieg, 0=Remis, 2=Niederlage für alle vier Mannschaften.)
ck0815 Auf diesen Beitrag antworten »

Uff! Das ist ja schonmal weit mehr als von mir geschätzt! Und danke und klasse, das ging ja schnell. smile

Aber dazu kommen ja noch die nach dem ersten Spieltag möglichen drei
(3 3 0 0; 3 1 0 1; 1 1 1 1) und die nach dem zweiten, zum Beispiel 4 4 1 1. Kannst Du die mit Deinem Skript auch berechnen?

Wie gesagt, bei mir hapert's ja schon beim Übergang Spieltag 1 zu Spieltag 2. Und außerdem würd's mich ja tierisch interessieren, wie man das "professionell" berechnet.

Trotzdem schonmal vielen vielen Dank! smile

Gruß
C
HAL 9000 Auf diesen Beitrag antworten »

code:
1:
2:
3:
   3   3   0   0  :  -  1/ -1 / 2- /2  -
   3   1   1   0  :  -  1/ -0 / 0- /2  -
   1   1   1   1  :  -  0/ -0 / 0- /0  -

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
   6   6   0   0  :  - 11/ -11/22- /22 -
   6   4   1   0  :  - 11/ -01/20- /22 -
   6   3   3   0  :  - 11/ -21/21- /22 -
   6   2   1   1  :  - 11/ -00/20- /20 -
   4   4   2   0  :  - 01/ -01/00- /22 -
   4   4   1   1  :  - 10/ -01/20- /02 -
   4   3   3   1  :  - 10/ -21/21- /02 -
   4   2   2   1  :  - 01/ -00/00- /20 -
   3   3   3   3  :  - 21/ -12/12- /21 -
   2   2   2   2  :  - 00/ -00/00- /00 -


Zitat:
Original von ck0815
Und außerdem würd's mich ja tierisch interessieren, wie man das "professionell" berechnet.

Sehr professionell war das bei mir nicht, da ich in Brute-force alle möglichen Ausgangskombinationen "Sieg/Remis/Niederlage" von 6 Partien berechnet habe. Wenn etwas mehr Mannschaften in der Gruppe sind, ist man mit dieser Methode schnell am Ende (bei 7 Mannschaften mit Kombinationsmöglichkeiten geht das gerade noch gut, aber dann ist Schluss).


EDIT: Hab gerade gemerkt, dass das für 2 Spieltage nicht stimmt, z.B. fehlt "4 4 3 0". Das Programm war ursprünglich auch nicht für "unvollständige" Austragungen konzipiert - hab gedacht, dass ich das schnell "hinferkeln" kann. Offenbar ein Irrtum.
ck0815 Auf diesen Beitrag antworten »

Aber das ist schonmal eine ganze Menge, das ist super. Wie hast Du das denn programmiert? Vielleicht checke ich das Programm zumindest und könnte mir dann eventuell fehlende Konstellationen für das Ende des zweiten Spieltags noch selber errechnen. Und vor allem nachvollziehen, was genau da gerechnet wird.

Gruß
C
HAL 9000 Auf diesen Beitrag antworten »

Ich hab es in C geschrieben und möchte den Programmcode besser nicht auflisten (schlechte Erfahrungen hier im Board).

Aber hier mal in Stichpunkten das Vorgehen.

1. Bei Teams (hier n=4) gibt es genau Partien (hier s=6).

2. Man kann also den Spielausgänge in einem Array der Länge (mit Elementen ) erfassen.
Dabei steht der Wert für den Ausgang des -ten Spiels (die C-Leute fangen immer bei 0 statt bei 1 an zu zählen Big Laugh ):
Wert 0 für Remis, Wert 1 für Sieg der ersten Mannschaft, Wert 2 für Sieg der zweiten Mannschaft

3. Für ein so ein kann man also durch Auswertung aller darin erfasster Spielausgänge die Punkteverteilung der vier Mannschaften berechnen.
Diese wird absteigend sortiert und zu einer (großen) Liste hinzugefügt.

4. Man beginnt mit "alles Null" in , berechnet dann jeweils die Punkteverteilung (siehe 3.), und schaltet dann zum nächstmöglichen , in alphabetischer Reihenfolge. D.h., bei wäre dies

000000
000001
000002
000010
000011
000012
000020
...
222222

das sind insgesamt mögliche Arrays (hier demnach 3^6=729).

5. Die in 3. nach und nach erzeugte Liste wird (wiederum alphabetisch) geordnet und Mehrfacheinträge eliminiert. Es verbleiben im Fall n=4,s=6 dann eben die genannten 40 echt verschiedenen Listeneinträge.



Das war es eigentlich schon. Da ich mir keine Gedanken um Spieltage gemacht habe, sondern das gleich ganzheitlich für alle Paarungen betrachtet habe, ist es schwierig, dies mit den Spieltagen nachträglich doch noch mit reinzubringen.

Außerdem habe ich 3. noch dahingehend variiert, dass ich von vornherein nur Ergebnisse in die Liste aufgenommen habe, wo die Punktergebnisse auch ohne vorgenommene Sortierung schon absteigend geordnet sind! Das kann man machen, denn letztendlich taucht jede (unsortierte) Punktverteilung in irgendeiner Permutation der Spielergebnisse dann auch nochmal "richtig" geordnet auf, d.h., man verpasst da nichts. Das ist dann aber auch der Grund, warum bei "unvollständigen" Spielen wie deinen Spieltagstabellen diese Betrachtung nicht klappt, daher fehlten oben beim 2.Spieltag zwei Ergebnisreihen.


P.S.: Bis zu mit dann klappt das noch ganz gut. mit würde bereits mehr als einen Tag Rechenzeit erfordern, bei mit wird's bereits astronomisch - da muss man sich dann intelligenteres als diese grobe Holzhammermethode einfallen lassen. Augenzwinkern
 
 
ck0815 Auf diesen Beitrag antworten »

Hallo HAL!

Ich bin derzeit ziemlich im Streß und konnte mir das noch nicht so genau anschauen, das sieht aber sehr ausführlich und interessant aus. Aber ich möchte mich hiermit auf jeden Fall schonmal ganz herzlich bedanken! Und melde mich dann wieder.

Schöne Tage
Christian
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »