Ottimizza la complessità dell'algoritmo combinatorio (2)
Sto cercando di trovare un modo per ottimizzare il calcolo per il seguente problema:
Ti vengono fornite N caselle indicizzate da 1 a N. Ogni casella contiene 0, 1 o 2 monete. Il numero di caselle con 0, 1 o 2 monete è indicato rispettivamente con n0, n1 e n2. Prendi un sottoinsieme casuale delle caselle in cui ogni sottoinsieme ha la stessa probabilità di essere selezionato. L'insieme vuoto e l'insieme stesso sono considerati un sottoinsieme. Qual è la probabilità che il numero totale di monete in un sottoinsieme casuale sia divisibile per 3.
Vincolo: N = n0 + n1 + n2 <100000
ESEMPI
12
- Ingresso: n0 = 0, n1 = 1, n2 = 0
- Uscita: 0,5
- Spiegazione: ci sono due sottoinsiemi: [] e 1 . Solo la somma di [] è un multiplo di 3.
3
- Ingresso: n0 = 0, n1 = 2, n2 = 0
- Uscita: 0,25
- Spiegazione: sono disponibili quattro sottoinsiemi: [], 1 , 1 e [1, 1]. Solo la somma di [] è un multiplo di 3.
- Ingresso: n0 = 1, n1 = 1, n2 = 1
- Uscita: 0,5
- Spiegazione: ci sono otto sottoinsiemi e i seguenti quattro hanno una somma che è un multiplo di 3: [], [0], [1, 2] e [0, 1, 2].
La mia implementazione in 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
Il risultato non sembra banale, ma dopo aver giocato con il numero compaiono degli schemi: si danno risultati simili quando si cambiano i numeri; per esempio. n0= 10, n1= 700, n2= 100dà lo stesso risultato ( 0.11111) di n0=11, n1=600, n2= 201; quindi ci deve essere un modo per semplificare il calcolo
Questa domanda è correlata alla mia domanda precedente .
Ho provato a implementare la soluzione proposta da Mike, ma devo aver fatto qualcosa di sbagliato in quanto il risultato non è corretto e ci vogliono anni per calcolare:
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)
AGGIORNAMENTO 2 (Soluzione): Ecco il codice che mi viene in mente, dopo la seconda risposta di Mike. Grazie mille per l'aiuto ancora!
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]
Risposte
Inserendo una seconda risposta poiché è abbastanza diversa.
Permettere $p(n,0)$ essere la probabilità che il numero di monete sia congruente $0\pmod 3$ quando ci sono $n$ scatole con una moneta e zero scatole con $0$ o $2$monete. Allo stesso modo, lascia$p(n,1)$ e $p(n,2)$ essere la probabilità che il numero di monete scelte sia $\equiv 1\pmod 3$ e $\equiv 2\pmod 3$in questo scenario. Considerando se il numero di casella$n$ è scelto, ottieni la ricorsione $$ 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)\\ $$ Adesso molla $\vec p(n)$ essere il vettore colonna $[p(n,0)\quad p(n,1)\quad p(n,2)]^T$. Le equazioni di cui sopra possono essere riassunte come un'equazione di matrice $$ \vec p(n) = \begin{bmatrix}\frac12&0&\frac12\\\frac12&\frac12&0\\0&\frac12&\frac12\end{bmatrix}\vec p(n-1) $$ Iterando questa ricorsione e lasciando $A$ essere la matrice di $\frac12$ e $0$ sopra, hai capito $$ \vec p(n)=A^n\vec p(0) $$ Pertanto, se puoi calcolare la potenza della matrice $A^n$ rapidamente, quindi puoi trovare $\vec p(n)$velocemente. Puoi calcolare$A^n$ nel $O(\log n)$ tempo utilizzando l'elevazione a potenza per quadratura.
Finora, abbiamo risolto il caso speciale in cui $n_2=0$. Locazione$q(n,0)$ essere la probabilità che il numero di monete sia $\equiv 0\pmod 3$ quando ci sono $n$ scatole con $2$ monete e nient'altro, allo stesso modo per $q(n,1)$ e $q(n,2)$, uno schema simile consente di calcolare il vettore $\vec q(n)$velocemente. Infine, lasciando$f(n_1,n_2)$ sii la probabilità che desideri quando ci sono $n_1$ scatole da una moneta e $n_2$ scatole da due monete, ottieni $$ 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). $$
La tua soluzione è più o meno lineare in $n_1,n_2$. Possiamo farlo logaritmicamente in$n_1,n_2$ come segue.
Permettere $X_{n_1,n_2}$ essere la variabile casuale uguale al resto $\pmod 3$ del numero di monete quando ci sono $n_1$ scatole con una moneta e $n_2$ con $2$. Nota che$n_0$non è referenziato, poiché non influenza la distribuzione di probabilità. La distribuzione di probabilità di$X_{n_1,n_2}$ è descritto da tre numeri che si sommano a $1$, o più succintamente da due di quei numeri $P(X_{n_1,n_2}\equiv 0\pmod 3)$ e $P(X_{n_1,n_2}\equiv 1\pmod 3)$.
Possiamo calcolare queste probabilità ricorsivamente come segue. Immagina di dividere le scatole per monete in due metà più o meno uguali, una rossa e una blu, e lo stesso per le due scatole per monete. Permettere$Y$ essere il numero di monete blu selezionate e lasciare $Z$ essere il numero di monete rosse selezionate, in modo che $X_{n_1,n_2}=Y+Z$. Quindi utilizzando$\equiv$ per significare "modulo congruente $3$", noi abbiamo $$ 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) $$ Questo porta immediatamente a un algoritmo ricorsivo, poiché $Y$ e $Z$ sono variabili casuali simili descritte da parametri che sono la metà delle dimensioni.