Wie mische ich Farbkugeln?

Ich habe 400 Bälle, von denen 100 rot, 40 gelb, 50 grün, 60 blau, 70 lila und 80 schwarz sind. (Kugeln der gleichen Farbe sind identisch)

Ich brauche einen effizienten Mischalgorithmus, damit die Bälle nach dem Mischen in einer Liste stehen und

3 aufeinanderfolgende Bälle haben nicht die gleiche Farbe. zB kann ich nicht "rot, rot, rot, gelb ..." haben

Und es ist "wahrscheinlich", dass alle Permutationen auftreten. (Nun, wenn der Kompromiss zwischen Effizienz und Unparteilichkeit gut genug ist, macht mir mehr Effizienz als Unparteilichkeit nichts aus).

Ich habe versucht, Fisher-Yates-Knuth anzupassen, aber das Ergebnis ist nicht ideal.

Warum Fisher-Yates nicht gut genug? Während des Geschäftsjahres nimmt Monte Carlo die inverse Transformation an. Und die Ausgabeverteilung behandelt dieselben Farbkugeln unterschiedlich, dh sie würde ein verzerrtes Ergebnis für meine Bedürfnisse erzeugen.

Und das naive Denken wäre, alle schlechten Permutationen aus dem gesamten Raum herauszufiltern / zurückzuverfolgen. Wenn die Einschränkung sehr stark ist, sagen wir, wenn wir nur 300 Bälle haben und 100 davon rot sind, gibt es zu viele Rückverfolgungen / Fehler, bevor eine geeignete Permutation erhalten wird.

Letztendlich möchte ich also in der Lage sein, alle guten Permutationen zu durchlaufen. Da die Anzahl der gültigen Permutationen jedoch zu groß ist, kann ich nur einige davon zufällig auswählen. Ich möchte, dass die statistischen Merkmale der "einige" der Bevölkerung so weit wie möglich ähneln.

Damit eine Markov-Kette zu einer gleichmäßigen Verteilung über alle möglichen Sequenzen von Bällen konvergiert, ist sie reversibel: Die Wahrscheinlichkeit, sich von Sequenz zu Sequenz j zu bewegen, ist dieselbe wie die Bewegung in die entgegengesetzte Richtung. Ich schlage daher vor, dass Sie die folgenden Züge verwenden (mit einer festen Wahrscheinlichkeitsverteilung, um auszuwählen, welche Art von Zug ausgeführt werden soll), um eine Markov-Kette für alle möglichen Sequenzen durchzuführen. Im Folgenden ist ein "Lauf" eine aufeinanderfolgende Teilsequenz von Kugeln gleicher Farbe mit maximaler Länge. Diese Markov-Kette setzt voraus, dass mindestens drei Farben vorhanden sind.$i$$j$

1. Wähle zwei Läufe nach dem Zufallsprinzip. Wenn Sie sie austauschen können und dennoch eine rechtliche Reihenfolge haben, tun Sie dies.

2. Wählen Sie zwei benachbarte Läufe. Wenn Sie sie austauschen können und dennoch eine rechtliche Reihenfolge haben, tun Sie dies.

3. Wählen Sie zwei Läufe derselben Farbe. Verteilen Sie die darin enthaltenen Bälle nach dem Zufallsprinzip auf die zulässigen Möglichkeiten (wenn also die maximale Anzahl von Bällen in einem einzelnen Lauf 3 betrug und Sie in den beiden ausgewählten Läufen insgesamt 5 Bälle hatten, ist es gleich wahrscheinlich, dass der erste 2 oder 3 Bälle erhält; wenn Es gab insgesamt 3 Bälle, der erste wird gleich wahrscheinlich 1 oder 2 bekommen; wenn es insgesamt 4 Bälle gab, sind 1, 2 und 3 alle gleich wahrscheinlich).

4. Wähle zufällig eine Farbe . Betrachten Sie die Sequenz S ' von Kugeln, wobei alle Kugeln der Farbe C i entfernt sind. Wählen Sie nun zufällig zwei Punkte in S 'aus, an denen sich benachbarte Kugeln unterschiedlicher Farben berühren.$C_i$$S'$$C_i$$S'$

   ein. Wenn an diesen beiden Punkten in der ursprünglichen Sequenz S zwei Farbläufe vorhanden sind und keiner die maximale Länge hat, bewegen Sie einen Ball von einem zum anderen, wobei jede Richtung mit einer Wahrscheinlichkeit von ½ gewählt wird.$C_i$$S$

   b. Wenn an diesen beiden Punkten in der ursprünglichen Sequenz S zwei Läufe der Farbe vorhanden sind , einer jedoch die maximale Länge und der andere nicht, bewegen Sie einen Ball mit der Wahrscheinlichkeit ½ vom maximalen Längenlauf zum kürzeren.$C_i$$S$

   c. Wenn es an einem dieser beiden Punkte in S nur einen Lauf der Farbe , bewegen Sie mit einer Wahrscheinlichkeit von ½ eine Kugel vom Lauf zum anderen Punkt. $C_i$$S$

   $C_i$

Wenn meine Analyse richtig ist, handelt es sich um eine reversible Markov-Kette, die schließlich zu einer gleichmäßigen Verteilung der legalen Sequenzen farbiger Kugeln konvergiert. Wenn Sie diese Kette also lange genug laufen lassen, kommen Sie dieser gleichmäßigen Verteilung sehr nahe.

$n_{i,k}$$i$$k$

$$\sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} },$$ $r$$m_{i,j}$ Stellen, an denen unmittelbar auf einen Farbverlauf der Farbe folgt (also ). Der Beitrag davon zur Entropie ist Dabei ist die Anzahl der Farben. $i$$j$$m_{i,i}=0$ $$\sum_i \ \log_2\ { \sum_j m_{i,j} \choose m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} },$$ $c$

(Im Interesse der Genauigkeit möchte ich darauf hinweisen, dass wir eine Reihe von Beiträgen zur Entropie auslassen, einschließlich der Farbe des ersten Balls, aber dies sind Begriffe niedrigerer Ordnung, die sicher vernachlässigt werden sollten.)

AKTUALISIEREN:

Es sollte Möglichkeiten geben, dies zu beschleunigen. Ich glaube, dass Sie für die Schritte c und d die Analyse verwenden können, um beide Schritte über alle Läufe einer Farbe gleichzeitig auszuführen. Für die Schritte a und b entspricht dies der Frage, eine zufällige Folge farbiger Kugeln mit der Einschränkung zu finden, dass sich keine zwei Kugeln derselben Farbe berühren. Es sollte eine gute Möglichkeit geben, dieses Problem zu mischen. Dann müssen Sie nur noch a / b-Schritte mit c / d-Schritten abwechseln, wobei sich jeder Schritt vollständig über diese beiden Züge mischt. Ich denke, dies sollte ziemlich schnell konvergieren, obwohl ich keine strenge Analyse für diese Markov-Kette habe.

Wie Sie sagten, ist es nicht möglich, sicherzustellen, dass jede Permutation gleich wahrscheinlich ist und dass die Farben gleichmäßig verteilt sind, da eine der Permutationen alle Rottöne in einer Reihe aufweist.

Eine sehr elegante, aber sicherlich nicht offensichtliche Methode, um sicherzustellen, dass die Farben gleichmäßig verteilt sind, besteht darin, eine Sequenz mit geringer Diskrepanz zu nutzen.

Angenommen, Sie haben Bälle, nummeriert von bis , und einen Startwert, .$N=400$$1$$N$$s$

Stellen Sie sicher, dass alle Kugeln derselben Farbe fortlaufend nummeriert sind. Das heißt, in Ihrem Fall lassen Sie die ersten 100 Bälle rot, die nächsten 40 gelb, die nächsten 50 grün usw. sein.

dann dem Ball den Wert so zu, dass: wobei$k^{\textrm{th}}$$x_k$

$$x_k = (s+ k \phi) \; (\textrm{mod}\; 1),$$

• $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$ , der goldene
• der Operator , der den Bruchteil des Arguments übernimmt$(\textrm{mod} \; 1)$
• $s$ ist ein beliebiger konstanter Startwert, den Sie wünschen.

Das heißt, jeder der Kugeln wird ein Wert von zugewiesen, der immer zwischen 0 und 1 liegt.$N$$x_k$

Ordnen Sie nun einfach die Kugeln in aufsteigender Reihenfolge nach ihrem Wert.$x_k$

Unter Verwendung des Startwerts von werden die Kugeln beispielsweise wie folgt geordnet: $s=0$B

$$\{B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,G,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,B,Y,K,B,R,P,Y,K,B,R,P,G,R,P,Y,K,B,R,P,G,K,R,B,R,K,G,R,P,Y,K,B,R,P,G,K,R,P,Y,K,B,R,P,G,K \}$$ (wobei "$B$"= Blau und" "= Schwarz).$K$

Schließlich, wenn Sie eine andere Probe nehmen möchten, einfach einen anderen Startwert auswählen, .$s$

Der Python-Code für die Zuweisung von lautet wie folgt:$x_k$

n=400

phi = (1+pow(5,0.5))/2
x = np.zeros(n)                 
s = np.random.uniform(0,1)
for i in range(n):
    x = (s + phi*(i+1)) %1

print (s)
print (x)