# pastebin

Paste Search Dynamic
Recent pastes
classify state
1. def classify_state(ar):
2.     r= len(ar)
3.     ab = []
4.     nab = []
5.     for i in range(r):
6.         _sum = sum(ar[i])
7.         if _sum != 0:
8.             nab.append(i)
9.         else:
10.             ab.append(i)
11.     return ab, nab
12.
13. #create R & Q
14. def create_RQ(ar, ab, nab):
15.
16.     n= len(ab)
17.     m= len(nab)
18.
19.     _RQ= []
20.     for i in range(m):
21.         _sum = float(sum(ar[nab[i]]))
22.
23.         temp= []
24.         for j in range(n):
25.             temp.append(ar[ nab[i]][ab[j] ] /_sum)
26.
27.         for j in range(m):
28.             temp.append(ar[ nab[i]][nab[j] ] /_sum)
29.
30.         _RQ.append(temp)
31.         del temp
32.
33.     R = []
34.     Q = []
35.     for i in range(len(_RQ)):
36.         R.append(_RQ[i][:n])
37.         Q.append(_RQ[i][n:])
38.
39.     del _RQ
40.     return R, Q
41.
42. #Creates an identity matrix
43. def create_In(n):
44.     In = []
45.     for i in range(n):
46.         temp= [0]*n
47.         temp[i]= 1
48.         In.append(temp)
49.     return In
50.
51. #Performs matrix-inversion
52. def invert(M):
53.     n = len(M)
54.     inv = create_In(n)
55.     for i in range(n):
56.         x = M[i][i]
57.         for k in range(n):
58.             M[i][k] = M[i][k] / x
59.             inv[i][k] = inv[i][k] / x
60.
61.         for j in range(n):
62.             if j == i:
63.                 continue
64.             x = M[j][i]
65.             for k in range(n):
66.                 inv[j][k] = round(inv[j][k] - x*inv[i][k], 5)
67.                 M[j][k] = M[j][k] - x*M[i][k]
68.     return inv
69.
70. #Creates the FUndamental matrix
71. def create_F(Q):
72.     m = len(Q)
73.     In= create_In(m)
74.     for i in range(m):
75.         for j in range(m):
76.             In[i][j] = In[i][j] - Q[i][j]
77.     return invert(In)
78.
79. #F == F[0, :]
80. def matrix_multiply(F, R):
81.     n= len(R[0])
82.     m= len(F)
83.     probs = []
84.     for i in range(n):
85.         _sum = 0
86.         for j in range(m):
87.             _sum += F[j] * R[j][i]
88.         probs.append(_sum)
89.     return probs
90.
91. #Converts decimal to fractions
92. def decimal_2_fraction(probs):
93.     from fractions import Fraction
94.
95.     fractions= []
96.     for i in probs:
97.         f= Fraction(i).limit_denominator(max_denominator= 100)
98.         fractions.append((f.numerator, f.denominator))
99.     return fractions
100.
101. def compute_lcm(x, y):
102.
103.    # choose the greater number
104.     if x > y:
105.         greater = x
106.     else:
107.         greater = y
108.
109.     while(true):
110.         if((greater % x == 0) and (greater % y == 0)):
111.             lcm = greater
112.             break
113.         greater += 1
114.
115.     return lcm
116.
118.     n = len(fracs)
119.
120.     lcm= fracs[0][1]
121.     for i in range(1, n):
122.         lcm= compute_lcm(lcm, fracs[i][1])
123.
125.     for i in range(n):
126.         mul= int(lcm/fracs[i][1])
129.
131.
132. def solution(ip):
133.     ab, nab = classify_state(ip)
134.     R, Q = create_RQ(ip, ab, nab)
135.     print(R)
136.     print(Q)
137.     F= create_F(Q)
138.     probs= matrix_multiply(F[0], R)
139.     fracs= decimal_2_fraction(probs)