Alle Kombinationen von einer Menge

Swoncen

Hallo!

Entweder ich hab gerade eine völlige Blockade, oder es ist wirklich nicht so leicht. Ich brauch folgendes:

Ich hab eine zufällig große Menge, sagen wir aus 7 Elementen. Nun möchte ich alle Kombinationen herausfinden, sodass immer 2 Elemente 2 anderen gegenüberstehen.

Ist jetzt schlecht erklärt, ich erklär wofür ichs brauch. Wir wollen ein Wuzzlturnier machen und es ist nicht klar wieviele Teilnehmer mitspielen. Klar ist jedenfalls, dass wir immer 2 gegen 2 spielen. Es sollten alle Kombinationen gespielt werden. Mir fällt grad nicht ein, wie ich das programmiern soll. Bitte um schnelle Hilfe.

Lynx

Du musst zuerst alle Möglichkeiten von 4 Leuten aus der Menge ziehen, also (7 über 4), im Beispiel mit 7 Leuten wären das 35. Dann musst du aus den 4 alle Kombinationen von paarweisen Gegenüberstellungen nehmen. Bei 4 Leuten, die du in 2 gegen 2 einteilen willst, sind das (4 über 2) / 2, also 3 Möglichkeiten.

Bei 7 Leuten kannst du dich mit 105 Spielen also auf einen langen Abend gefasst machen. Sollten doch 8 Leute kommen, werdens 210 Spiele (wobei man da aber zumindest einige gleichzeitig spielen kann). Wenn ihr Glück habt, kommen nur 6 und ihr müsst nur 45 mal spielen (plant trotzdem schon mal ein Wochenende ein )

Swoncen

Hallo!

Ja wieviele Spiele es sein werden ist mir schon klar, aber ich hätte gerne die Paarungen. Zum Beispiel

a, b, c, d

a+b gegen c+d
a+c gegen b+d
a+d gegen b+c

aber jetzt wo ich das so aufschreib, fällt mir schon was ein. Trotzdem danke für die Hilfe =)

Swoncen

Ok ich habs soweit. Ist in php geschrieben, und schaut so aus:

PHP

for($i=0;$i<sizeof($this->players);$i++)
            for($j=0;$j<sizeof($this->players);$j++)
                for($k=0;$k<sizeof($this->players);$k++)
                    for($l=0;$l<sizeof($this->players);$l++)
                    {
                        if($i==$j || $i==$k || $i==$l || $j==$k || $j==$l || $k==$l)
                            break;
                        echo $this->players[$i]->name,"+",$this->players[$j]->name," - ";
                        echo $this->players[$k]->name,"+",$this->players[$l]->name,"<BR>";
                    }

$this->players sind die Spieler, wie man sich denken kann. Das einzige Problem ist, dass es jetzt auch eine Rückrunde gibt. Also bei 6 Spielern sinds nicht 45 Spiele, sondern 90. Wenn jemand eine schnelle Lösung weiß, bitte bescheid sagen.

Lynx

fang nicht bei jeder Schleife bei 0 an, sondern bei dem wert der letzten Schleife + 1.

PHP

for($i=0;$i<sizeof($this->players);$i++)
            for($j=i+1;$j<sizeof($this->players);$j++)
                for($k=j+1;$k<sizeof($this->players);$k++)
                    for($l=k+1;$l<sizeof($this->players);$l++)
                    {
                        echo $this->players[$i]->name,"+",$this->players[$j]->name," - ";
                        echo $this->players[$k]->name,"+",$this->players[$l]->name,"<BR>";
                    }

Das sollte Redundanzen eliminieren.

ist aber nur mal ein spontaner Einfall, wie er mir so in 5 minuten grad kommt. Passt vielleicht noch nicht 100%ig, aber in die Richtung müssts gehen.

Swoncen

Ja es stimmt nicht ganz, aber es ist ein guter Tipp.. Danke

Spockman

Zitat von Swoncen

Ist jetzt schlecht erklärt, ich erklär wofür ichs brauch. Wir wollen ein Wuzzlturnier machen und es ist nicht klar wieviele Teilnehmer mitspielen. Klar ist jedenfalls, dass wir immer 2 gegen 2 spielen. Es sollten alle Kombinationen gespielt werden. Mir fällt grad nicht ein, wie ich das programmiern soll. Bitte um schnelle Hilfe.

Hier in Prolog:

Code

:- op(600, xfx, gegen).


wuzzel(Ls, Plays) :-
    findall(P, wuzzel_(Ls, P), Plays).


wuzzel_(Ls0, Play) :-
    select(A, Ls0, Ls1),
    select(B, Ls1, Ls2),
    B @> A,
    select(C, Ls2, Ls3),
    C @> A,
    select(D, Ls3, _),
    D @> C,
    Play = (A + B) gegen (C + D).

Alles anzeigen

Getestet mit SWI-Prolog. Beispiel-Query:

Code

?- wuzzel([a,b,c,d], P).


P = [a+b gegen c+d, a+c gegen b+d, a+d gegen b+c] ;

Swoncen

Ich hab keine Ahnung vom Prolog, aber ist egal, ich habs schon geschafft. Ich geb jedem Spieler eine eindeutige Zahl (Potenz von 2) und speicher dann die begegnungen in einem Array. Somit kommts nicht mehr doppelt vor. Habs gestern noch rechtzeitig vorm wuzzeln geschafft =).

PHP

for($i=0;$i<sizeof($this->players);$i++)
            $nmb[$i] = pow(2,($i+1));


        for($i=0;$i<sizeof($this->players);$i++)
            for($j=0;$j<sizeof($this->players);$j++)
                for($k=0;$k<sizeof($this->players);$k++)
                    for($l=0;$l<sizeof($this->players);$l++)
                    {
                        if($i==$j || $i==$k || $i==$l || $j==$k || $j==$l || $k==$l)
                            break;


                        if($rem[$nmb[$i]+$nmb[$j]][$nmb[$k]+$nmb[$l]]==true ||
                           $rem[$nmb[$k]+$nmb[$l]][$nmb[$i]+$nmb[$j]]==true)
                            break;


                        echo = $this->players[$i]->name."+".$this->players[$j]->name."-".$this->players[$k]->name."+".$this->players[$l]->name;


                        $rem[$nmb[$i]+$nmb[$j]][$nmb[$k]+$nmb[$l]]=true;
                        $rem[$nmb[$k]+$nmb[$l]][$nmb[$i]+$nmb[$j]]=true;
                    }

Alles anzeigen

Das Problem ist jetzt, dass die Spiele noch ungeordnet sind. Manche Spieler haben zeitweise viel mehr Spiele als andere, wobei es aber im Endeffekt aufs selbe rauskommt. Trotzdem gibts sicher eine schönere Methode, die zusätzlich noch die Ordnung herstellt.

Alle Kombinationen von einer Menge

Jetzt mitmachen!

Benutzer online in diesem Thema