Permutation - nur für die Hälfte?

[Monger]

Hallo,

für ein Programm brauche ich eine Permutation innerhalb einer Liste. Den Algorithmus habe ich, nur leider zieht der kräftig an der Performance (siehe weiter unten). Deshalb versuche ich, jetzt soweit zu optimieren wie möglich.

Ein kräftiger Schritt vorwärts wäre, wenn ich die Hälfte aller Permutationen ausschließen könnte, denn

ABCDEF

wäre in meinem Fall das selbe wie

DEFABC

Hat jemand eine Idee, wie ich folgenden Algorithmus abändern könnte, um das zu erreichen? Fällt euch vielleicht noch etwas auf, was ich optimieren könnte?


private boolean rekursiveUmtauschung(List<Spieler> anfang, List<Spieler> rest) {

// Ist nur noch ein Spieler am Ende da, muss das eine neue Kombination
// sein
if (rest.size() == 1) {
List<Spieler> kombination = new ArrayList<Spieler>(anfang);
kombination.addAll(rest);
boolean isOK = standardPaarung(kombination);
if(isOK){
return isOK;
}
} else {
// bei mehreren wähle immer einen und setze ihn mit an den Anfang
for (int i = 0; i < rest.size(); i++) {

List<Spieler> rest_neu = new ArrayList<Spieler>(rest.subList(0, 0 + i));
rest_neu.addAll(rest.subList(i + 1, rest.size()));

List<Spieler> anfang_neu = new ArrayList<Spieler>(anfang);
anfang_neu.addAll(rest.subList(i, i + 1));
boolean isOk = rekursiveUmtauschung(anfang_neu, rest_neu);
if(isOk){
return isOk;
}
}
}
return false;
}

[Demirug]

Sehe ich das Richtig das du für eine Menge von Spielern jede mögliche Parrung berechnen willst. Dabei soll aber jeder nur einmal gegen jeden Spielen müssen?

[Trap]

für ein Programm brauche ich eine Permutation innerhalb einer Liste.
[...]
ABCDEF
wäre in meinem Fall das selbe wie
DEFABC

Beschreib dein Problem mal ordentlich. Oder ruf beim Fernseh-Hellseher an, der kann dir vielleicht auch ohne Beschreibung helfen ;)

[Pinoccio]

Permutation innerhalb einer ListeSchau mal hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?t=242107), dortiges Thema scheint ähnlich zu sein.

mfg Sebastian

[Monger]

Sehe ich das Richtig das du für eine Menge von Spielern jede mögliche Parrung berechnen willst. Dabei soll aber jeder nur einmal gegen jeden Spielen müssen?

Ja, genau. Das ist für einen Tischtennisverein, der das Schweizer Turniersystem verwendet.

Was hier gemacht wird, ist folgendes:

Eine Reihe von Spielern wird sortiert, und damit die Rekursion begonnen. Bei jeder Kombination wird die Spielerliste in zwei Hälften geteilt, und gepaart.
Also z.B.

ABC DE -> A vs D, B vs E

Das geht solange, bis entweder eine gültige Paarung zustandekommt, oder alle Kombinationsmöglichkeiten durchgespielt wurden. Deshalb meldet sich die korrekte Paarung durch ein "isOK", damit der Algorithmus abgebrochen werden kann.
Spätestens wenn die Hälfte aller Spieler ausgetauscht wurden, wurden alle Kombinationsmöglichkeiten erreicht, weil

DEC AB -> D vs A, E vs B

das selbe ist wie das Beispiel oben. Genau das fehlt mir aber noch in diesem Algorithmus.


Schau mal hier, dortiges Thema scheint ähnlich zu sein.

mfg Sebastian

Genau aus diesem Thread stammt überhaupt die Idee, das ganze über Permutationen zu lösen. Aber das Problem ist hier ein wenig anders. Ich speicher z.B. erst gar nicht alle möglichen Lösungen ab, sondern suche nur die erste mögliche Lösung. Mein Problem ist, dass wenn es überhaupt keine Lösung gibt, die Rekursion bis zur letzten Möglichkeit durchläuft, und derzeit vieles doppelt macht.

Edit: Außerdem hab ich bereits ausgeschlossen, dass in meiner Liste zwei identische Spieler vorkommen. Die relativ aufwendige Diskussion über aussortieren von gleichen Ergebnissen, die in dem anderen Thread geführt wurde, erübrigt sich also in diesem Fall.

Editedit: Übrigens ist natürlich auch jede Mischform redundant.

AB CDE -> A vs C, B vs D

ist genau das selbe wie

CB ADE -> C vs A, B vs D

[littlejam]

Warum machst du es nicht, wie in der Mathematik üblich?
Sprich: du gehst jedes Element des Arrays durch und kombinierst das mit den verbleibenden Elementen.
ABCDEF:
AB AC AD AE AF
BC BD BE BF
CD CE CF
DE DF
EF

So hast du doch alle möglichen Kombinationen einfach.

Gruß

[Monger]

Warum machst du es nicht, wie in der Mathematik üblich?
Sprich: du gehst jedes Element des Arrays durch und kombinierst das mit den verbleibenden Elementen.
ABCDEF:
AB AC AD AE AF
BC BD BE BF
CD CE CF
DE DF
EF

So hast du doch alle möglichen Kombinationen einfach.

Gruß

Edit: Argh, hab was falsches geschrieben. Was du hier beschreibst, ist ja nicht n! , sondern quasi Fakultät mit Addition, als 5+4+3+2+1 ...
Ja, das könnte hinhauen. Das müsste etwa der Aufwand sein, den ich brauche. Vom Verfahren her ist es aber nicht richtig, weil es auch eine Rolle spielt, wie die verbleibenden Elemente kombiniert werden.

In deinem Beispiel:
Wenn ich mir AC wähle, müssen noch die verbleibenden Paarungen kombiniert werden. Und da sind BD EF, BE DF und BF ED möglich. Ausserdem ist die Reihenfolge wichtig. So wie derzeit die Permutation läuft, ist es völlig richtig, aber ab einem gewissen Punkt treten halt nur noch bereits getestete Kombinationen auf.

Ich überlege grade, ob ich nicht einfach am Anfang grob die Menge aller Durchläufe berechne, und die Rekursion dann abbreche wenn X Durchläufe durchlaufen worden sind. Dazu muss ich mir aber sicher sein was für ein Aufwand das ist. Wenn ich zu niedrig schätze, schneide ich mit Sicherheit notwendige Lösungen ab.

[fabnet2k]

ou, klingt nach schwerster mathematik ?

[mapel110]

ou, klingt nach schwerster mathematik ?
Ich rate dir, die sinnlosen Kommentare einzustellen. So kommst du nicht auf den Marktplatz.

[Monger]

Ich glaube, ich bin selber auf eine deutliche Verbesserung gekommen.

Die Grundidee ist, dass sobald auch nur eine bekannte Paarung vorkommt, dieser Rekursionszweig überhaupt nicht mehr weiterverfolgt werden muss. Eine Paarung kam bereits dann schonmal vor, wenn das aktuell getauschte Element größer ist als das andere. Also z.B.



ABC DEF -> Alles Ok, von hier aus dürfen weitere Kombinationen gebildet werden.

AEC DBF -> E ist größer als B. Paarungen in dieser Kombination kamen also schonmal vor, also kann man alle Varianten mit E vs B komplett streichen.

Das reduziert die Rechenzeit spürbar. Ich schätze, etwa von O( n ) -> (n - 1)! auf O (n ) -> (n - 1) / 2 !
Wen es interessiert, hier ist nochmal der überarbeitete Quellcode. Vielleicht sind ja solche Vereinfachungen auch auf andere Probleme anwendbar...

PS: thx @ Pinoccio! Falls es dir nicht aufgefallen ist: ich hab die Rekursion von dir aus dem anderen Thread geklaut! Ich hoffe dir macht es nix aus. Ist auch für nichtkommerzielle Zwecke! :)

private boolean rekursiveUmtauschung(List<Spieler> anfang, List<Spieler> rest) {

// Ist nur noch ein Spieler am Ende da, muss das eine neue Kombination
// sein
if (rest.size() == 1) {
List<Spieler> kombination = new ArrayList<Spieler>(anfang);
kombination.addAll(rest);
boolean isOK = standardPaarung(kombination);
if(isOK){
return isOK;
}
} else {
// bei mehreren wähle immer einen und setze ihn mit an den Anfang
for (int i = 0; i < rest.size(); i++) {

List<Spieler> rest_neu = new ArrayList<Spieler>(rest.subList(0, 0 + i));
rest_neu.addAll(rest.subList(i + 1, rest.size()));

List<Spieler> anfang_neu = new ArrayList<Spieler>(anfang);
anfang_neu.addAll(rest.subList(i, i + 1));
boolean isOk = false;
if(doProceed(anfang_neu, rest_neu)){
isOk = rekursiveUmtauschung(anfang_neu, rest_neu);
}

if(isOk){
return isOk;
}
}
}
return false;
}


private boolean doProceed(List<Spieler> anfang, List<Spieler> rest){

Spieler zupruefenderSpieler = rest.get(0);
List<Spieler> kombination = new ArrayList<Spieler>(anfang);
kombination.addAll(rest);

int index = kombination.indexOf(zupruefenderSpieler);
Spieler andererSpieler;
if(index < mitte){
andererSpieler = kombination.get(index + mitte);
if(zupruefenderSpieler.compareTo(andererSpieler) < 0){
return true;
}
}
else{
andererSpieler = kombination.get(index - mitte);
if(zupruefenderSpieler.compareTo(andererSpieler) > 0){
return true;
}
}


return false;
}

[P2oldi]

Also wenn ich das richtig verstehe, willst Du ein kartesisches Produkt ohne Dopplungen haben, also bei A,B,C,D soll im Endeffekt AB, AC, AD, BC, BD, CD rauskommen richtig?

Realisierung in Java:

public static void main(String[] args)
{
List l = new ArrayList();
l.add("A");
l.add("B");
l.add("C");
l.add("D");

for(int i = 0; i < l.size(); i++)
{
for(int j = 0; j < l.size(); j++)
{
if(i < j)
System.out.println(l.get(i) + " " + t.get(j));
}
}
}

Ausgabe:
A B
A C
A D
B C
B D
C D


das bringt das gewünschte Ergebnis, und das sogar relativ fix. Sollte es nicht das sein, was Du willst, vergiß es einfach :)

[Monger]

das bringt das gewünschte Ergebnis, und das sogar relativ fix. Sollte es nicht das sein, was Du willst, vergiß es einfach :)

Leider nicht was ich brauche! ;)
Ich muss ALLE Elemente miteinander kombinieren, nicht nur zwei. Und ich MUSS optimieren, sonst komme ich bei 30-40 Elementen in bedrohliche Laufzeiten hinein. Ein Glück hab ich das momentan einigermaßen im Griff...

[P2oldi]

das versteh ich grade net ganz :)
Weil wenn Du alle Elemente miteinander kombinierst (in meinem Beispiel dann woh A,B,C,D), kommt doch nur ein gültiger Satz raus, wenn Du Dopplungen vermeidest oder nicht?
Nämlich ABCD... es sei denn, Sachen wie AABC, AABD etc. wären auch möglich... ist es das?
vielleicht kannst Du mir mal ein Beispiel geben, wie die Eingabe aussieht, und wie die Ausgabe dann aussehen soll? *verwirrt ist*

[littlejam]

Ich glaube das Problem ist nicht, die möglichen Kombinationen zu finden.
Es geht um ein Turniersystem, da reichen nicht alle möglichen Kombinationen. Es sollten möglichst alle gleichzeitig spielen und nur einmal gegeneinander.
Die möglichen Kombinationen müssen daher auch noch sinnvoll miteinander kombiniert werden.

ABCD:
AB AC AD BC BD CD

1. Runde
AB CD
2. Runde
AC BD
3. Runde
AD BC

Bei 4 Teilnehmern mag das noch gehen, aber bei 40 brauchts halt nen anständigen Algorithmus :)

Ist eigentlich eine Optimale Spielverteilung ohne Doppelung möglich?

Sprich bei 6 Spielern nur 5 Runden zu je 3 Spielen?

Gruß

[Monger]

Bei 4 Teilnehmern mag das noch gehen, aber bei 40 brauchts halt nen anständigen Algorithmus :)

Ist eigentlich eine Optimale Spielverteilung ohne Doppelung möglich?

Sprich bei 6 Spielern nur 5 Runden zu je 3 Spielen?

Gruß

Ja, ist sie.

Genau dazu gibt es das Schweizer Turniersystem. Die Permutation hier ist nur ein kleiner (wenn auch wesentlicher) Ausschnitt dieser Paarungsregeln.

Der Witz an dem Schweizer System ist, dass es ständig dafür sorgt, dass Spieler mit ähnlicher Spielstärke gegeneinander spielen, und sich so die Spieltabelle sehr schnell ausprägt. Man muss also bei 40 Spielern keine 39 Spiele machen, um einen eindeutigen Sieger zu haben, sondern nur 6 oder 7.

Die Permutation ist eigentlich nur dafür da, von allen Kombinationsmöglichkeiten die erste zu finden. Dass Spieler so gruppiert werden, dass auch faire Paarungen zustande kommen, ist mit ganz anderen Mitteln sichergestellt.

das versteh ich grade net ganz :)
Weil wenn Du alle Elemente miteinander kombinierst (in meinem Beispiel dann woh A,B,C,D), kommt doch nur ein gültiger Satz raus, wenn Du Dopplungen vermeidest oder nicht?
Nämlich ABCD... es sei denn, Sachen wie AABC, AABD etc. wären auch möglich... ist es das?
vielleicht kannst Du mir mal ein Beispiel geben, wie die Eingabe aussieht, und wie die Ausgabe dann aussehen soll? *verwirrt ist*

Nehmen wir mal ABCD. Dann haben wir 5 gültige Kombinationsmöglichkeiten:

ABCD, ABDC, ACBD, BACD, BADC ... eigentlich sind es 24, aber aufgrund der Art, wie aus dieser Liste Paarungen gebildet werden, sind die meisten davon redundant.

Beispiel:

ACBD -> AC | BD -> A vs B , C vs D
ADBC -> AD | BC -> A vs B , D vs C Ist genau das selbe, also unnötig


Von den 5 Möglichkeiten könnte ich mir die letzten zwei (BACD, BADC) auch noch sparen, weil diese Paarung - wenn auch in anderer Paarungs-Reihenfolge - auch bereits schonmal ausgetestet wurde. Ich hab nur noch nicht herausgefunden, wie ich die auch noch filtern kann, oder ob das Nebenwirkungen z.B. bei ungerader Spielerzahl geben würde.