¿Cómo barajar bolas de colores?

Tengo 400 bolas, en las cuales 100 son rojas, 40 son amarillas, 50 son verdes, 60 son azules, 70 son moradas, 80 son negras. (las bolas del mismo color son idénticas)

Necesito un algoritmo de barajado eficiente, para que después de barajar, las bolas estén en una lista, y

Cualquier 3 bolas consecutivas no son del mismo color. por ejemplo, no puedo tener "rojo, rojo, rojo, amarillo ..."

Y, toda permutación es "igualmente" probable que ocurra. (bueno, si el equilibrio entre eficiencia e imparcialidad es lo suficientemente bueno, no me importa más eficiencia que imparcialidad).

Traté de adaptar Fisher-Yates-Knuth, pero el resultado no es el ideal.

¿Por qué Fisher-Yates no es lo suficientemente bueno? A medida que FY adopta la transformación inversa de Monte Carlo. Y la distribución de salida trata las bolas del mismo color de manera diferente, es decir, generaría un resultado sesgado para mis necesidades.

Y, el pensamiento ingenuo sería filtrar / retroceder todas las permutaciones malas de todo el espacio. Cuando la restricción es muy fuerte, digamos, si tenemos solo 300 bolas y 100 de las cuales son rojas, entonces habrá demasiados fallos / seguimiento de retroceso antes de obtener una permutación adecuada.

Entonces, en última instancia, me gustaría poder iterar a través de todas las buenas permutaciones. Sin embargo, debido a que el número de permutaciones válidas es demasiado grande, solo puedo muestrear al azar algunas de ellas. Quiero que la característica estadística de "algunos" de ellos se parezca lo más posible a la población.

Lo que necesita para que una cadena de Markov converja a una distribución igual sobre todas las secuencias posibles de bolas es reversible: la probabilidad de pasar de la secuencia a la secuencia j es la misma que moverse en la dirección opuesta. Por lo tanto, propongo que utilice los siguientes movimientos (con una distribución de probabilidad fija para elegir qué tipo de movimiento realizar) para realizar una cadena de Markov en todas las secuencias posibles. A continuación, una "carrera" es una subsecuencia consecutiva de longitud máxima de bolas del mismo color. Esta cadena de Markov se basa en que haya al menos tres colores.$i$$j$

1. Elige dos carreras al azar. Si puede intercambiarlos y todavía tiene una secuencia legal, hágalo.

2. Elige dos carreras adyacentes. Si puede intercambiarlos y todavía tiene una secuencia legal, hágalo.

3. Elige dos carreras del mismo color. Redistribuya las bolas en ellas al azar entre las posibilidades legales (por lo tanto, si el número máximo de bolas en una sola carrera fue 3, y tuvo 5 bolas en total en las dos carreras elegidas, la primera es igualmente probable que obtenga 2 o 3 bolas; si hubo 3 bolas en total, la primera es igualmente probable que obtenga 1 o 2; si hubo 4 bolas en total, 1, 2 y 3 son igualmente probables).

4. Elige un color al azar. Considere la secuencia S ' de bolas con todas las bolas de color C i eliminadas. Ahora, elija al azar dos puntos en S ' donde se tocan bolas adyacentes de diferentes colores.$C_i$$S'$$C_i$$S'$

   a. Si hay dos carreras de color en estos dos puntos en la secuencia original S , y ninguna de las dos es la longitud máxima, mueva una pelota de una a la otra, con cada dirección elegida con probabilidad ½.$C_i$$S$

   si. Si hay dos carreras de color en estos dos puntos en la secuencia original S , pero una es de longitud máxima y la otra no, mueva una bola de la carrera de longitud máxima a la más corta con probabilidad ½.$C_i$$S$

   C. Si solo hay una carrera de color en uno de estos dos puntos en S , con probabilidad ½ mover una bola de la carrera al otro punto. $C_i$$S$

   re. Si no hay corrida de color en ninguno de estos puntos, o si hay corridas de longitud máxima en ambos puntos, no haga nada.$C_i$

Si mi análisis es correcto, esta es una cadena de Markov reversible que finalmente converge a una distribución uniforme de secuencias legales de bolas de colores, por lo que si ejecuta esta cadena durante el tiempo suficiente, se acercará mucho a esta distribución uniforme.

¿Cómo puedes saber cuando esto ha convergido? Sugeriría ver la entropía de esta secuencia, y detenerse cuando deje de aumentar. ¿Cómo se calcula la entropía? Hay dos términos principales en el cálculo de la entropía: la distribución de las longitudes de ejecución y la secuencia de colores que tiene cada ejecución. Para la distribución de las longitudes de ejecución, suponga que hay ejecuciones de color i con longitud k . La contribución de estos a la entropía es donde es la longitud máxima permitida de una carrera. Ahora, consideremos la contribución de la secuencia de colores a la entropía. Supongamos que hay$n_{i,k}$$i$$k$rmi,jijmi,i=0Σiconecto2(Σjmi,

$$\sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} },$$ $r$$m_{i,j}$ lugares donde una secuencia de color es seguida inmediatamente por una de color (entonces ). La contribución de esto a la entropía es donde es el número de colores. $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$

(En aras de la precisión, permítanme señalar que estamos dejando de lado una serie de contribuciones a la entropía, incluido el color de la primera bola, pero estos son términos de orden inferior que deberían ser seguros de descuidar).

ACTUALIZAR:

Debería haber formas de acelerar esto. Creo que para los pasos cyd, puede usar el análisis para realizar estos dos pasos en todas las ejecuciones de un color a la vez. Para los pasos ayb, esto es equivalente a la cuestión de encontrar una secuencia aleatoria de bolas de colores con la restricción de que no toquen dos bolas del mismo color. Debería haber una buena forma de mezclar para este problema. Luego solo tiene que alternar los pasos a / b con los pasos c / d, donde cada paso se mezcla sobre esos dos movimientos por completo. Creo que esto debería converger bastante rápido, aunque no tengo ningún análisis riguroso para esta cadena de Markov.

Como dijiste, no es posible asegurar que cada permutación sea igualmente probable y que los colores se distribuyan uniformemente, porque una de las permutaciones tiene todos los rojos en una fila.

Un método muy elegante, pero ciertamente no obvio, para garantizar que los colores se distribuyan uniformemente es aprovechar una secuencia de baja discrepancia.

Suponga que tiene bolas, numeradas del al , y un valor inicial, .$N=400$$1$$N$$s$

Asegúrese de que todas las bolas del mismo color estén numeradas consecutivamente. Es decir, en su caso, deje que las primeras 100 bolas sean rojas, las siguientes 40 sean amarillas, las siguientes 50 verdes, etc.

Luego, asigne a la bola el valor, tal que: donde$k^{\textrm{th}}$$x_k$

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

• $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$ , la proporción áurea
• el que toma la parte fraccionaria del argumento$(\textrm{mod} \; 1)$
• $s$ es cualquier valor 'semilla' constante que desee.

Es decir, a cada una de las bolas se le asignará un valor de que siempre estará entre 0 y 1.$N$$x_k$

Ahora simplemente ordene las bolas, en orden ascendente de acuerdo con su valor .$x_k$

Por ejemplo, usando el valor semilla de , las bolas se ordenarán de la siguiente manera: $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 \}$$ (donde "$B$"= Azul y" "= Negro).$K$

Finalmente, si desea tomar una muestra diferente, simplemente seleccione un valor semilla diferente, .$s$

El código de Python para esta asignación de es el siguiente:$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)