Optimizar la complejidad del algoritmo combinatorio (2)
Estoy tratando de encontrar una manera de optimizar el cálculo para el siguiente problema:
Se le dan N casillas indexadas del 1 al N. Cada casilla contiene 0, 1 o 2 monedas. El número de cajas con 0, 1 o 2 monedas se indican con n0, n1 y n2 respectivamente. Se toma un subconjunto aleatorio de casillas donde cada subconjunto tiene la misma probabilidad de ser seleccionado. El conjunto vacío y el conjunto en sí se consideran un subconjunto. ¿Cuál es la probabilidad de que el número total de monedas en un subconjunto aleatorio sea divisible por 3?
Restricción: N = n0 + n1 + n2 <100000
EJEMPLOS
12
- Entrada: n0 = 0, n1 = 1, n2 = 0
- Salida: 0.5
- Explicación: Hay dos subconjuntos: [] y 1 . Solo la suma de [] es múltiplo de 3.
3
- Entrada: n0 = 0, n1 = 2, n2 = 0
- Salida: 0,25
- Explicación: Hay cuatro subconjuntos: [], 1 , 1 y [1, 1]. Solo la suma de [] es múltiplo de 3.
- Entrada: n0 = 1, n1 = 1, n2 = 1
- Salida: 0.5
- Explicación: Hay ocho subconjuntos y los cuatro siguientes tienen una suma que es un múltiplo de 3: [], [0], [1, 2] y [0, 1, 2].
Mi implementación en Python 3.8:
prob = 0
for j in range(0, n1+1):
for k in range(0, n2+1):
if j == k:
prob += comb(n1, j) * comb(n2, k)
elif (j % 3 == 0) & (k % 3 == 0):
prob += comb(n1, j) * comb(n2, k)
total_prob = (2**n0 * prob) / (2 ** (n0+n1+n2))
return total_prob
El resultado no parece trivial, pero después de jugar con el número, aparecen algunos patrones: se dan resultados similares al cambiar los números; p.ej. n0= 10, n1= 700, n2= 100da el mismo resultado ( 0.11111) que n0=11, n1=600, n2= 201; por lo tanto, debe haber alguna forma de simplificar el cálculo
Esta pregunta está relacionada con mi pregunta anterior .
Traté de implementar la solución propuesta por Mike, pero debo haber hecho algo mal ya que el resultado no es correcto y lleva años calcular:
def p_x_equals_i(n1, n2, i):
y_n1 = n1 // 2
y_n2 = n2 // 2
z_n1 = n1 // 2 + (n1 % 2)
z_n2 = n2 // 2 + (n2 % 2)
prob = 0
## i equals 0
if n1 == 1 and n2 ==0 and i == 0:
return 0.5
if n1 == 0 and n2 == 0 and i == 0:
return 1
if n1 == 0 and n2 ==1 and i == 0:
return 0.5
if n1 == 1 and n2 ==1 and i == 0:
return 0.5
## i equals 1
if n1 == 1 and n2 ==0 and i == 1:
return 0
if n1 == 0 and n2 == 0 and i == 1:
return 0
if n1 == 0 and n2 ==1 and i == 1:
return 0.5
if n1 == 1 and n2 ==1 and i == 1:
return 0.25
if i == 0:
return p_x_equals_i(y_n1, y_n2, 0) * p_x_equals_i(z_n1, z_n2, 0) +\
p_x_equals_i(y_n1, y_n2, 1) * \
( 1 - (p_x_equals_i(z_n1, z_n2, 0) + p_x_equals_i(z_n1, z_n2, 1))) + \
( 1 - (p_x_equals_i(y_n1, y_n2, 0) + p_x_equals_i(y_n1, y_n2, 1))) *\
p_x_equals_i(z_n1, z_n2, 1)
if i == 1:
return p_x_equals_i(y_n1, y_n2, 0) * p_x_equals_i(z_n1, z_n2, 1) +\
p_x_equals_i(y_n1, y_n2, 1) * p_x_equals_i(z_n1, z_n2, 0) +\
( 1 - (p_x_equals_i(y_n1, y_n2, 0) + p_x_equals_i(y_n1, y_n2, 1))) *\
( 1 - (p_x_equals_i(z_n1, z_n2, 0) + p_x_equals_i(z_n1, z_n2, 1)))
else:
print('error')
def recursive(n1, n2):
y_n1 = n1 // 2
y_n2 = n2 // 2
z_n1 = n1 // 2 + (n1 % 2)
z_n2 = n2 // 2 + (n2 % 2)
return p_x_equals_i(y_n1, y_n2, 0) * p_x_equals_i(z_n1, z_n2, 0) +\
p_x_equals_i(y_n1, y_n2, 1) * \
( 1 - (p_x_equals_i(z_n1, z_n2, 0) + p_x_equals_i(z_n1, z_n2, 1))) + \
( 1 - (p_x_equals_i(y_n1, y_n2, 0) + p_x_equals_i(y_n1, y_n2, 1))) *\
p_x_equals_i(z_n1, z_n2, 1)
ACTUALIZACIÓN 2 (Solución): Aquí está el código que se me ocurrió, siguiendo la segunda respuesta de Mike. ¡Muchas gracias por la ayuda nuevamente!
from numpy.linalg import matrix_power
import numpy as np
def p(n):
A = np.array([[0.5, 0, 0.5], [0.5, 0.5, 0], [0, 0.5, 0.5]])
p0 = [1, 0, 0]
return matrix_power(A, n).dot(p0)
def q(n):
B = np.array([[0.5, 0.5, 0],[0, 0.5, 0.5], [0.5, 0, 0.5]])
q0 = [1, 0, 0]
return matrix_power(B, n).dot(q0)
def f(n1, n2):
pn1 = p(n1)
qn1 = q(n1)
qn2 = q(n2)
return pn1[0] * qn2[0] + pn1[1] * qn2[2] + pn1[2] * qn2[1]
Respuestas
Publicar una segunda respuesta ya que es lo suficientemente diferente.
Dejar $p(n,0)$ sea la probabilidad de que el número de monedas sea congruente con $0\pmod 3$ cuando hay $n$ cajas con una moneda y cero cajas con $0$ o $2$monedas Del mismo modo, dejemos$p(n,1)$ y $p(n,2)$ sea la probabilidad de que el número de monedas elegidas sea $\equiv 1\pmod 3$ y $\equiv 2\pmod 3$en este escenario. Considerando si el número de casilla$n$ es elegido, obtienes la recursividad $$ p(n,0)=\tfrac12p(n-1,0)+\tfrac12p(n-1,2)\\ p(n,1)=\tfrac12p(n-1,1)+\tfrac12p(n-1,0)\\ p(n,2)=\tfrac12p(n-1,2)+\tfrac12p(n-1,1)\\ $$ Ahora deja $\vec p(n)$ ser el vector de columna $[p(n,0)\quad p(n,1)\quad p(n,2)]^T$. Las ecuaciones anteriores se pueden resumir como una ecuación matricial $$ \vec p(n) = \begin{bmatrix}\frac12&0&\frac12\\\frac12&\frac12&0\\0&\frac12&\frac12\end{bmatrix}\vec p(n-1) $$ Iterando esta recursividad y dejando $A$ ser la matriz de $\frac12$ y $0$ arriba, lo entiendes $$ \vec p(n)=A^n\vec p(0) $$ Por lo tanto, si puede calcular la potencia de la matriz $A^n$ rápidamente, entonces puedes encontrar $\vec p(n)$con rapidez. Puedes calcular$A^n$ en $O(\log n)$ tiempo usando exponenciación al cuadrado.
Hasta ahora, hemos resuelto el caso especial donde $n_2=0$. Dejando$q(n,0)$ sea la probabilidad de que el número de monedas sea $\equiv 0\pmod 3$ cuando hay $n$ cajas con $2$ monedas y nada más, de manera similar para $q(n,1)$ y $q(n,2)$, un esquema similar le permite calcular el vector $\vec q(n)$con rapidez. Finalmente, dejando$f(n_1,n_2)$ sea la probabilidad que desee cuando haya $n_1$ cajas de una moneda y $n_2$ cajas de dos monedas, obtienes $$ f(n_1,n_2) = p(n_1,0)q(n_2,0)+p(n_1,1)q(n_2,2)+p(n_1,2)q(n_2,1). $$
Su solución es aproximadamente lineal en $n_1,n_2$. Podemos hacer esto logarítmicamente en$n_1,n_2$ como sigue.
Dejar $X_{n_1,n_2}$ ser la variable aleatoria igual al resto $\pmod 3$ del número de monedas cuando hay $n_1$ cajas con una moneda, y $n_2$ con $2$. Tenga en cuenta que$n_0$no se hace referencia, ya que no afecta la distribución de probabilidad. La distribución de probabilidad de$X_{n_1,n_2}$ se describe mediante tres números que suman $1$, o más sucintamente por dos de esos números $P(X_{n_1,n_2}\equiv 0\pmod 3)$ y $P(X_{n_1,n_2}\equiv 1\pmod 3)$.
Podemos calcular estas probabilidades de forma recursiva de la siguiente manera. Imagínese dividir las cajas de una moneda en dos mitades aproximadamente iguales, una roja y otra azul, y lo mismo para las dos cajas de monedas. Dejar$Y$ sea el número de monedas azules seleccionadas, y deje $Z$ ser el número de monedas rojas seleccionadas, de modo que $X_{n_1,n_2}=Y+Z$. Luego usando$\equiv$ para significar "módulo congruente $3$", tenemos $$ P(X_{n_1,n_2}\equiv 0)=P(Y\equiv 0)P(Z\equiv 0)+P(Y\equiv 1)P(Z\equiv 2)+P(Y\equiv 2)P(Z\equiv 1)\\ P(X_{n_1,n_2}\equiv 1)=P(Y\equiv 0)P(Z\equiv 1)+P(Y\equiv 1)P(Z\equiv 0)+P(Y\equiv 2)P(Z\equiv 2) $$ Esto conduce inmediatamente a un algoritmo recursivo, ya que $Y$ y $Z$ son variables aleatorias similares descritas por parámetros que son la mitad del tamaño.