Optimiser la complexité de l'algorithme combinatoire (2)
J'essaie de trouver un moyen d'optimiser le calcul pour le problème suivant:
Vous recevez N boîtes indexées de 1 à N. Chaque boîte contient 0, 1 ou 2 pièces. Le nombre de cases avec 0, 1 ou 2 pièces est noté respectivement n0, n1 et n2. Vous prenez un sous-ensemble aléatoire des cases où chaque sous-ensemble a la même probabilité d'être sélectionné. L'ensemble vide et l'ensemble lui-même sont considérés comme un sous-ensemble. Quelle est la probabilité que le nombre total de pièces dans un sous-ensemble aléatoire soit divisible par 3.
Contrainte: N = n0 + n1 + n2 <100000
EXEMPLES
12
- Entrée: n0 = 0, n1 = 1, n2 = 0
- Sortie: 0,5
- Explication: Il existe deux sous-ensembles: [] et 1 . Seule la somme de [] est un multiple de 3.
3
- Entrée: n0 = 0, n1 = 2, n2 = 0
- Sortie: 0,25
- Explication: Il existe quatre sous-ensembles: [], 1 , 1 et [1, 1]. Seule la somme de [] est un multiple de 3.
- Entrée: n0 = 1, n1 = 1, n2 = 1
- Sortie: 0,5
- Explication: Il existe huit sous-ensembles et les quatre suivants ont une somme multiple de 3: [], [0], [1, 2] et [0, 1, 2].
Mon implémentation 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
Le résultat ne semble pas anodin, mais après avoir joué avec le nombre, des motifs apparaissent: un résultat similaire est donné lors du changement des nombres; par exemple. n0= 10, n1= 700, n2= 100donne le même résultat ( 0.11111) que n0=11, n1=600, n2= 201; il doit donc y avoir un moyen de simplifier le calcul
Cette question est liée à ma question précédente .
J'ai essayé d'implémenter la solution proposée par Mike, mais j'ai dû faire quelque chose de mal car le résultat n'est pas correct, et le calcul prend des siècles:
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)
MISE À JOUR 2 (Solution): Voici le code que j'ai trouvé, suite à la deuxième réponse de Mike. Merci beaucoup pour l'aide encore!
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]
Réponses
Poster une deuxième réponse car elle est assez différente.
Laisser $p(n,0)$ être la probabilité que le nombre de pièces soit congru à $0\pmod 3$ quand il y a $n$ boîtes avec une pièce et zéro boîte avec $0$ ou $2$pièces de monnaie. De même, laissez$p(n,1)$ et $p(n,2)$ être la probabilité que le nombre de pièces choisies soit $\equiv 1\pmod 3$ et $\equiv 2\pmod 3$dans ce scénario. En considérant si oui ou non le numéro de boîte$n$ est choisi, vous obtenez la récursivité $$ 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)\\ $$ Maintenant, laisse $\vec p(n)$ être le vecteur de la colonne $[p(n,0)\quad p(n,1)\quad p(n,2)]^T$. Les équations ci-dessus peuvent être résumées comme une équation matricielle $$ \vec p(n) = \begin{bmatrix}\frac12&0&\frac12\\\frac12&\frac12&0\\0&\frac12&\frac12\end{bmatrix}\vec p(n-1) $$ Itérer cette récursion et laisser $A$ être la matrice de $\frac12$ et $0$ ci-dessus, vous obtenez ça $$ \vec p(n)=A^n\vec p(0) $$ Par conséquent, si vous pouvez calculer la puissance de la matrice $A^n$ rapidement, alors vous pouvez trouver $\vec p(n)$rapidement. Vous pouvez calculer$A^n$ dans $O(\log n)$ temps en utilisant l'exponentiation par quadrillage.
Jusqu'à présent, nous avons résolu le cas particulier où $n_2=0$. Location$q(n,0)$ être la probabilité que le nombre de pièces est $\equiv 0\pmod 3$ quand il y a $n$ boîtes avec $2$ pièces de monnaie et rien d'autre, de même pour $q(n,1)$ et $q(n,2)$, un schéma similaire vous permet de calculer le vecteur $\vec q(n)$rapidement. Enfin, laisser$f(n_1,n_2)$ être la probabilité que vous désirez quand il y a $n_1$ boîtes à une pièce et $n_2$ boîtes à deux pièces, vous obtenez $$ 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). $$
Votre solution est à peu près linéaire en $n_1,n_2$. Nous pouvons le faire de manière logarithmique en$n_1,n_2$ comme suit.
Laisser $X_{n_1,n_2}$ être la variable aléatoire égale au reste $\pmod 3$ du nombre de pièces lorsqu'il y a $n_1$ boîtes avec une pièce, et $n_2$ avec $2$. Notez que$n_0$n'est pas référencé, car il n'affecte pas la distribution de probabilité. La distribution de probabilité de$X_{n_1,n_2}$ est décrit par trois nombres additionnés à $1$, ou plus succinctement par deux de ces nombres $P(X_{n_1,n_2}\equiv 0\pmod 3)$ et $P(X_{n_1,n_2}\equiv 1\pmod 3)$.
Nous pouvons calculer ces probabilités récursivement comme suit. Imaginez diviser les boîtes à monnaie en deux moitiés à peu près égales, une rouge et une bleue, et la même chose pour les deux boîtes à monnaie. Laisser$Y$ être le nombre de pièces bleues sélectionnées, et laissez $Z$ être le nombre de pièces rouges sélectionnées, de sorte que $X_{n_1,n_2}=Y+Z$. Puis en utilisant$\equiv$ pour signifier "modulo congruent $3$", nous avons $$ 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) $$ Cela conduit immédiatement à un algorithme récursif, car $Y$ et $Z$ sont des variables aléatoires similaires décrites par des paramètres deux fois plus petits.