Ich habe ein paar Probleme, nur um zu versuchen, meinen Kopf programmatisch um dieses Problem zu wickeln. Das ist nicht genau was ich tue, aber um Dinge zu vereinfachen, sagen wir, dass wir eine bestimmte Anzahl von Bällen und eine bestimmte Anzahl von Leuten haben. Jede Person muss genau einen Ball wählen und die Leute dürfen auf die Art Ball beschränkt sein, die sie wählen können. Ziel ist es zu bestimmen, welche Optionen die Menschen wählen müssen, nachdem sie alle unmöglichen Kombinationen eliminiert haben.
In einem einfachen Fall sagen wir, wir haben zwei Leute und einen roten und einen grünen Ball. Person 1 kann einen Ball wählen, aber Person 2 kann nur den grünen Ball wählen. Dies kann wie folgt dargestellt werden:
%Vor%Da wir wissen, dass Person 2 den grünen Ball wählen muss, bedeutet dies, dass Person 1 diesen Ball nicht wählen kann und daher den roten Ball wählen muss. Dies kann vereinfacht werden zu:
%Vor%Also in diesem Fall wissen wir genau, was jede Person wählt.
Jetzt fügen wir ein bisschen Komplexität hinzu. Jetzt haben wir 4 Leute, die aus 2 roten, 1 grünen und 4 blauen Kugeln wählen müssen. Person 1 kann jeden Ball wählen, Person 2 und 3 können die roten oder grünen Bälle wählen und Person 4 muss einen roten Ball wählen. Also haben wir die folgenden Möglichkeiten:
%Vor%Da Person 4 nur eine Art von Option hat, wissen wir, dass diese Person einen roten Ball wählen muss. Wir können daher 1 roter Ball von allen anderen Menschen eliminieren:
%Vor%Aber hier wird es wirklich schwierig. Wie wir sehen können, müssen Person 2 und 3 einen roten und einen grünen Ball wählen, wir wissen einfach nicht, welcher Spieler welchen wählen wird. Da jedoch nur noch 1 von jedem Ball übrig ist, können Rot und Grün auch als Option von Person 1 eliminiert werden:
%Vor%Jetzt können wir von jedem Eintrag Duplikate entfernen, die mit den folgenden Optionen übrig bleiben:
%Vor%Wir kennen die Wahl von Person 1 und Person 4, und Person 2 und 3 haben die Wahl zwischen Rot und Grün.
Um das zu lösen, was ich mache ist eine Schleife über die Leute und zuerst, wenn die Leute nur einen Balltyp haben, entferne diese Person aus dem Array und lege sie in das Ergebnis-Array (da ich weiß, dass diese Person wählen muss ) und entferne dann einen dieser Balltypen von jeder anderen Person im Array, falls vorhanden.
Danach scheint mir die Regel so zu sein:
Wenn es
$nAnzahl von Leuten gibt, die alle die gleiche$nAnzahl von haben Optionen (oder eine Teilmenge davon) können diese Optionen entfernt werden von allen anderen Leuten, wo$nkleiner ist als die Gesamtzahl der Leute.
Was ich also tue, ist, die Leute wieder zu durchlaufen und nach anderen Leuten zu suchen, die die gleichen Optionen haben (oder eine Teilmenge dieser Optionen) und wenn das gleich der Gesamtzahl von Optionen für diese Person ist, entferne sie aus die Optionen für alle anderen Leute.
Hier ist, was ich bis jetzt habe, die diese zwei Fälle lösen werden:
%Vor%
Dies ergibt folgendes Ergebnis:
%Vor%Dieses Beispiel funktioniert nicht mit dem obigen Code. Angenommen, es gibt 1 rote Kugel, 1 grüne Kugel, 1 blaue Kugel, 1 gelbe Kugel und 4 Personen. Person 1 kann jeden Ball wählen, Person 2 kann rot oder grün wählen, Person 3 kann grün oder blau wählen, Person 4 kann rot oder blau wählen.
Visuell würde das so aussehen:
%Vor%Da die 3 Farben rot, grün und blau die einzigen Optionen für die Personen 2, 3 und 4 sind, sind sie vollständig innerhalb dieser 3 Personen enthalten und können daher alle von Person 1 eliminiert werden, was bedeutet, dass Person 1 gelb wählen muss . Wenn Person 1 alles andere als gelb wählen würde, wäre es unmöglich für die anderen Leute, ihre Bälle zu wählen.
Wenn ich es in mein PHP-Programm setze, habe ich folgende Eingabewerte:
%Vor%Aber ich kann mir nicht vorstellen, wie ich durchgehen muss, um solche Fälle zu finden, ohne jede einzelne mögliche Kombination von Menschen durchlaufen zu müssen. Irgendwelche Ideen, wie das gemacht werden könnte?
Am Ende entschied ich mich dafür, eine semi Brute-Force zu sein, aber ich habe es so optimiert, dass es nicht jede einzelne Kombination durchlaufen muss, also sollte es in den meisten Fällen
Die Gesamtzahl der Kombinationen ist gleich exp(2,count(balls)) (dh 2 ^ {Arten von Bällen}), also wenn wir 20 Arten von Bällen haben, sind das 1048576 verschiedene Kombinationen von Bällen, die wir überprüfen müssten, wenn wir es wären überprüfe jeden. Das sind nicht nur zu viele Iterationen, ich habe schon vorher mit nur 16 Ballfarben den Speicher ausgespart.
Um jede einzelne Kombination zu erhalten, können Sie diese Funktion verwenden ( Quelle ):
%Vor%Wenn wir jedoch zu unserer ursprünglichen Regel zurückkehren:
Wenn es $ n Anzahl von Leuten gibt, die alle die gleiche Anzahl von Optionen haben (oder eine Teilmenge von ihnen), können diese Optionen von allen anderen Personen entfernt werden, wobei $ n kleiner ist als die Gesamtzahl der Personen .
Wie wir sehen können, können wir zukünftige Iterationen überspringen, wenn wir $n Anzahl der Optionen bereits überschritten haben. Beachten Sie, wenn wir mehrere Zahlen der gleichen Ballfarbe haben, die in dieser Funktion als mehrere Bälle zählen.
Sobald wir die verschiedenen möglichen Untermengen erhalten haben, durchlaufen wir die Personen, um zu sehen, ob wir $n verschiedene Personen haben, die diese Untergruppe verwenden, und diese Werte von allen anderen Personen entfernen. Dies ist, was ich am Ende herausgefunden habe:
Das scheint für alle Werte zu funktionieren, die ich ausprobiert habe. Im obigen Beispiel haben wir 4 verschiedene Ballfarben (2 ^ 4 = 16 Gesamtkombinationen), aber wir müssen nur 6 Iterationen in unserer getBallSubsets() -Funktion durchführen, also ist dies viel effizienter als das rohe Erzwingen jeder einzelnen möglichen Kombination.
Ich bevorzuge einen eher OOP-ähnlichen Ansatz. Also habe ich im Grunde von vorne angefangen. Ich hoffe es geht dir gut.
Also, das folgende sieht (zugegebenermaßen) ziemlich hässlich aus und ich habe es bis jetzt mit nichts außer Ihren drei Beispielen getestet, aber hier geht es:
%Vor%Das Ganze heißt so:
%Vor%Und ebenso für Beispiel 3:
%Vor%Ich habe die ursprüngliche Ausgabe der Kürze halber weggelassen. Aber für das zweite Beispiel entspricht es im Wesentlichen Ihrer letzten entsprechenden Auflistung in der Frage und für Beispiel 3 ergibt es das Äquivalent von:
%Vor%Tags und Links php combinatorics combinations