pastebin

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.  
  117. def final_answer(fracs):
  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.  
  124.     answer = []
  125.     for i in range(n):
  126.         mul= int(lcm/fracs[i][1])
  127.         answer.append( fracs[i][0]*mul )
  128.     answer.append(lcm)
  129.  
  130.     return answer
  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)
  140.     ans= final_answer(fracs)
  141.     return ans
  142.  
  143. ip= [[0, 1, 0, 0, 0, 1], [4, 0, 0, 3, 2, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
  144. sol= [0, 3, 2, 9, 14]
  145. ans= solution(ip)
  146.  
  147. print(ans)
Parsed in 0.039 seconds