Otimize a complexidade do algoritmo combinatório (2)
Estou tentando encontrar uma maneira de otimizar o cálculo para o seguinte problema:
Você recebe N caixas indexadas de 1 a N. Cada caixa contém 0, 1 ou 2 moedas. O número de caixas com 0, 1 ou 2 moedas são denotados como n0, n1 e n2, respectivamente. Você pega um subconjunto aleatório de caixas onde cada subconjunto tem a mesma probabilidade de ser selecionado. O conjunto vazio e o próprio conjunto são considerados um subconjunto. Qual é a probabilidade de que o número total de moedas em um subconjunto aleatório seja divisível por 3.
Restrição: N = n0 + n1 + n2 <100000
EXEMPLOS
12
- Entrada: n0 = 0, n1 = 1, n2 = 0
- Produto: 0,5
- Explicação: Existem dois subconjuntos: [] e 1 . Apenas a soma de [] é um múltiplo de 3.
3
- Entrada: n0 = 0, n1 = 2, n2 = 0
- Saída: 0,25
- Explicação: Existem quatro subconjuntos: [], 1 , 1 e [1, 1]. Apenas a soma de [] é um múltiplo de 3.
- Entrada: n0 = 1, n1 = 1, n2 = 1
- Produto: 0,5
- Explicação: Existem oito subconjuntos e os quatro seguintes têm uma soma que é um múltiplo de 3: [], [0], [1, 2] e [0, 1, 2].
Minha implementação em 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
O resultado não parece trivial, mas depois de brincar com o número, alguns padrões aparecem: resultados semelhantes são fornecidos ao alterar os números; por exemplo. n0= 10, n1= 700, n2= 100dá o mesmo resultado ( 0.11111) que n0=11, n1=600, n2= 201; portanto, deve haver alguma maneira de simplificar o cálculo
Essa pergunta está relacionada à minha pergunta anterior .
Tentei implementar a solução proposta por Mike, mas devo ter feito algo errado, pois o resultado não está correto e leva muito tempo para 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)
ATUALIZAÇÃO 2 (Solução): Aqui está o código que eu criei, seguindo a 2ª resposta de Mike. Muito obrigado pela ajuda novamente!
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]
Respostas
Postando uma segunda resposta, pois é diferente o suficiente.
Deixei $p(n,0)$ ser a probabilidade de que o número de moedas seja congruente com $0\pmod 3$ quando há $n$ caixas com uma moeda e zero caixas com $0$ ou $2$moedas. Da mesma forma, vamos$p(n,1)$ e $p(n,2)$ ser a probabilidade de que o número de moedas escolhidas seja $\equiv 1\pmod 3$ e $\equiv 2\pmod 3$Neste cenário. Ao considerar se o número da caixa ou não$n$ é escolhido, você obtém a recursão $$ 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)\\ $$ Agora deixe $\vec p(n)$ seja o vetor coluna $[p(n,0)\quad p(n,1)\quad p(n,2)]^T$. As equações acima podem ser resumidas como uma equação matricial $$ \vec p(n) = \begin{bmatrix}\frac12&0&\frac12\\\frac12&\frac12&0\\0&\frac12&\frac12\end{bmatrix}\vec p(n-1) $$ Iterando esta recursão, e permitindo $A$ seja a matriz de $\frac12$ e $0$ acima, você entendeu $$ \vec p(n)=A^n\vec p(0) $$ Portanto, se você pode calcular a potência da matriz $A^n$ rapidamente, então você pode encontrar $\vec p(n)$rapidamente. Você pode calcular$A^n$ no $O(\log n)$ tempo usando exponenciação por quadratura.
Até agora, resolvemos o caso especial em que $n_2=0$. De locação$q(n,0)$ seja a probabilidade do número de moedas ser $\equiv 0\pmod 3$ quando há $n$ caixas com $2$ moedas e nada mais, da mesma forma para $q(n,1)$ e $q(n,2)$, um esquema semelhante permite que você calcule o vetor $\vec q(n)$rapidamente. Finalmente, deixando$f(n_1,n_2)$ seja a probabilidade que você deseja quando há $n_1$ caixas de uma moeda e $n_2$ caixas de duas moedas, você obtém $$ 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). $$
Sua solução é aproximadamente linear em $n_1,n_2$. Podemos fazer isso logaritmicamente em$n_1,n_2$ do seguinte modo.
Deixei $X_{n_1,n_2}$ ser a variável aleatória igual ao resto $\pmod 3$ do número de moedas quando há $n_1$ caixas com uma moeda, e $n_2$ com $2$. Observe que$n_0$não é referenciado, pois não afeta a distribuição de probabilidade. A distribuição de probabilidade de$X_{n_1,n_2}$ é descrito por três números que somam $1$, ou mais sucintamente por dois desses números $P(X_{n_1,n_2}\equiv 0\pmod 3)$ e $P(X_{n_1,n_2}\equiv 1\pmod 3)$.
Podemos calcular essas probabilidades recursivamente da seguinte maneira. Imagine dividir as caixas de uma moeda em duas metades aproximadamente iguais, uma vermelha e uma azul, e o mesmo para as duas caixas de moedas. Deixei$Y$ seja o número de moedas azuis selecionadas, e deixe $Z$ ser o número de moedas vermelhas selecionadas, de modo que $X_{n_1,n_2}=Y+Z$. Então usando$\equiv$ para significar "módulo congruente $3$", temos $$ 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) $$ Isso leva imediatamente a um algoritmo recursivo, uma vez que $Y$ e $Z$ são variáveis aleatórias semelhantes descritas por parâmetros que têm metade do tamanho.