326 lines
8.9 KiB
Python
326 lines
8.9 KiB
Python
class Fraction:
|
|
def __init__(self, num, den):
|
|
if num < 1 and num > 0:
|
|
self.num = num*100
|
|
self.den = 100
|
|
else:
|
|
self.num = num
|
|
self.den = den
|
|
self._simplify()
|
|
|
|
def __str__(self):
|
|
return str(self.num) + "/" + str(self.den)
|
|
|
|
def __radd__(self, other):
|
|
return self.__add__(other)
|
|
|
|
def __rsub__(self, other):
|
|
return self.__sub__(other)
|
|
|
|
def __rmul__(self, other):
|
|
return self.__mul__(other)
|
|
|
|
def __rdiv__(self, other):
|
|
return self.__div__(other)
|
|
|
|
def __add__(self, other):
|
|
if isinstance(other, self.__class__):
|
|
if self.den == other.den:
|
|
return Fraction(self.num + other.num, self.den)
|
|
else:
|
|
num = self.num * other.den + other.num * self.den
|
|
den = self.den * other.den
|
|
return Fraction(num, den)
|
|
elif isinstance(other, int):
|
|
return Fraction(self.num + (other * self.den), self.den)
|
|
|
|
def __sub__(self, other):
|
|
if isinstance(other, self.__class__):
|
|
if self.den == other.den:
|
|
return Fraction(self.num - other.num, self.den)
|
|
else:
|
|
return Fraction(((self.num * other.den)-(other.num*self.den)),self.den * other.den)
|
|
elif isinstance(other, int):
|
|
if other == 0:
|
|
return Fraction(-self.num, self.den)
|
|
else:
|
|
return Fraction(self.num - (other * self.den), self.den)
|
|
elif isinstance(other, float):
|
|
if other == 0:
|
|
return Fraction(-self.num, self.den)
|
|
else:
|
|
return Fraction(self.num - (other * self.den), self.den)
|
|
|
|
def __mul__(self, other):
|
|
if isinstance(other, self.__class__):
|
|
num = self.num * other.num
|
|
den = self.den * other.den
|
|
return Fraction(num, den)
|
|
elif isinstance(other, int):
|
|
return self * Fraction(other, 1)
|
|
elif isinstance(other, float):
|
|
return self * Fraction(other, 1)
|
|
|
|
def __div__(self, other):
|
|
if isinstance(other, self.__class__):
|
|
num = self.num * other.den
|
|
den = self.den * other.num
|
|
return Fraction(num, den)
|
|
elif isinstance(other, int):
|
|
return self / Fraction(other, 1)
|
|
|
|
def getNum(self):
|
|
return self.num
|
|
|
|
def getDen(self):
|
|
return self.den
|
|
|
|
def _gcf(self, first, second):
|
|
while second:
|
|
first, second = second, first % second
|
|
return first
|
|
|
|
def _simplify(self):
|
|
if self.den == 0:
|
|
return
|
|
gcf = self._gcf(self.num, self.den)
|
|
self.num = self.num / gcf
|
|
self.den = self.den / gcf
|
|
|
|
class Matrix:
|
|
def __init__(self, m):
|
|
self.matrix = [[0 for i in range(len(m[0]))] for j in range(len(m))]
|
|
for i, row in enumerate(m):
|
|
for j, col in enumerate(row):
|
|
self.matrix[i][j] = m[i][j]
|
|
self.I = []
|
|
self.R = []
|
|
self.Q = []
|
|
|
|
def __str__(self):
|
|
textArr = ""
|
|
for row in self.matrix:
|
|
for col in row:
|
|
if type(col) == int:
|
|
textArr += " " + str(col) + " "
|
|
else:
|
|
textArr += str(col) + " "
|
|
textArr += "\n"
|
|
return textArr
|
|
|
|
def __len__(self):
|
|
return len(self.matrix)
|
|
|
|
def __getitem__(self, i):
|
|
return self.matrix[i]
|
|
|
|
def __radd__(self, other):
|
|
return self.__add__(other)
|
|
|
|
def __rsub__(self, other):
|
|
return self.__sub__(other)
|
|
|
|
def __rmul__(self, other):
|
|
return self.__mul__(other)
|
|
|
|
def __add__(self, other):
|
|
result = [[0 for i in range(len(other.matrix[0]))] for j in range(len(other.matrix[0]))]
|
|
if isinstance(other, self.__class__):
|
|
for i in range(len(self.matrix)):
|
|
for j in range(len(other.matrix[0])):
|
|
result[i][j] = other.matrix[i][j] + other.matrix[i][j]
|
|
elif isinstance(other, int):
|
|
return "TODO: Matrix Add Function w/ Int"
|
|
return result
|
|
|
|
def __sub__(self, other):
|
|
if isinstance(other, self.__class__):
|
|
if len(self.matrix) < len(other.matrix):
|
|
short = self
|
|
else:
|
|
short = other
|
|
result = [[0 for i in range(len(short.matrix[0]))] for j in range(len(short.matrix[0]))]
|
|
for i in range(len(short.matrix)):
|
|
for j in range(len(short.matrix[0])):
|
|
result[i][j] = self.matrix[i][j] - other.matrix[i][j]
|
|
elif isinstance(other, int):
|
|
return "TODO: Matrix Sub Function w/ Int"
|
|
return result
|
|
|
|
def __mul__(self, other):
|
|
A = self
|
|
B = other
|
|
result = [[sum(a * b for a, b in zip(A_row, B_col))
|
|
for B_col in zip(*B)]
|
|
for A_row in A]
|
|
return result
|
|
|
|
def getMatrix(self):
|
|
return self.matrix
|
|
|
|
def getI(self):
|
|
return self.I
|
|
|
|
def getR(self):
|
|
return self.R
|
|
|
|
def getQ(self):
|
|
return self.Q
|
|
|
|
def makeRegAndSTD(self):
|
|
m = self.matrix
|
|
shift = 0
|
|
# Point Terminal states to themselves and move to top of 2d array
|
|
for i, row in enumerate(m):
|
|
void = True
|
|
for col in row:
|
|
if col != 0:
|
|
void = False
|
|
if void == True:
|
|
row[i] = 1
|
|
m.insert(shift, row)
|
|
m.pop(i+1)
|
|
shift += 1
|
|
|
|
# Shift all elements relative to the nmber of terminal states found
|
|
for i, row in enumerate(m):
|
|
m[i] = m[i][-shift:] + m[i][:-shift]
|
|
|
|
# Extract sections of the matrix for use in calculating F
|
|
top = m[:shift]
|
|
bottom = m[shift:]
|
|
I = [[0 for i in range(len(m))] for j in range(shift)]
|
|
R = [[0 for i in range(len(m))] for j in range(len(m)-shift)]
|
|
Q = [[0 for i in range(len(m))] for j in range(len(m)-shift)]
|
|
|
|
for i, col in enumerate(top):
|
|
I[i] = col[:shift]
|
|
|
|
for i, col in enumerate(bottom):
|
|
R[i] = col[:shift]
|
|
Q[i] = col[shift:]
|
|
|
|
self.I = Matrix(I)
|
|
self.R = Matrix(R)
|
|
self.Q = Matrix(Q)
|
|
|
|
def invertMatrix(AM, IM):
|
|
for fd in range(len(AM)):
|
|
fdScaler = 1.0 / AM[fd][fd]
|
|
for j in range(len(AM)):
|
|
AM[fd][j] *= fdScaler
|
|
IM[fd][j] *= fdScaler
|
|
for i in list(range(len(AM)))[0:fd] + list(range(len(AM)))[fd+1:]:
|
|
crScaler = AM[i][fd]
|
|
for j in range(len(AM)):
|
|
AM[i][j] = AM[i][j] - crScaler * AM[fd][j]
|
|
IM[i][j] = IM[i][j] - crScaler * IM[fd][j]
|
|
return IM
|
|
|
|
def fetchProbabilities(m):
|
|
nums = [0]*len(m[0])
|
|
dens = [0]*len(m[0])
|
|
results = [0]*len(m[0])
|
|
for i, col in enumerate(m[0]):
|
|
nums[i] = col.getNum()
|
|
dens[i] = col.getDen()
|
|
|
|
# RISK: both denominators might need to get changed (not just go into the biggest)
|
|
commonDen = dens[0]
|
|
for col in dens[1:]:
|
|
if col > commonDen:
|
|
commonDen = col
|
|
|
|
for i, col in enumerate(nums):
|
|
if dens[i] != commonDen:
|
|
results[i] = nums[i] * (commonDen / dens[i])
|
|
|
|
results.append(commonDen)
|
|
|
|
return results
|
|
|
|
def solution(m):
|
|
# Change probabilities to Fractions' for easy working
|
|
for i, row in enumerate(m):
|
|
den = 0
|
|
for j, col in enumerate(row):
|
|
den += m[i][j]
|
|
for j, col in enumerate(row):
|
|
if m[i][j] != 0 and den != 0:
|
|
m[i][j] = Fraction(m[i][j], den)
|
|
|
|
m = Matrix(m)
|
|
print "Input: \n" + m.__str__()
|
|
|
|
m.makeRegAndSTD()
|
|
print "STD: \n" + m.__str__()
|
|
|
|
iq = Matrix(m.getI() - m.getQ())
|
|
print "I-Q: \n" + iq.__str__()
|
|
|
|
F = invertMatrix(iq.getMatrix(), [[1,0],[0,1]])
|
|
print "F: \n" + F.__str__()
|
|
|
|
FR = Matrix(F * m.getR())
|
|
print "FR: \n" + FR.__str__()
|
|
|
|
return fetchProbabilities(FR)
|
|
|
|
|
|
|
|
|
|
# set1 = [
|
|
# [0, 2, 1, 0, 0],
|
|
# [0, 0, 0, 3, 4],
|
|
# [0, 0, 0, 0, 0],
|
|
# [0, 0, 0, 0,0],
|
|
# [0, 0, 0, 0, 0]
|
|
# ]
|
|
# set1Out = [7, 6, 8, 21]
|
|
|
|
|
|
set2 = [
|
|
[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]
|
|
]
|
|
set2Out = [0, 3, 2, 9, 14]
|
|
|
|
# set3 = [
|
|
# [1,0,0,0],
|
|
# [0,1,0,0],
|
|
# [0,0,1,0],
|
|
# [0,0,0,1]
|
|
# ]
|
|
# set3Out = [1, 1]
|
|
|
|
# case1 = solution(set1)
|
|
# if case1 == set1Out:
|
|
# print "Test 1: Passed"
|
|
# else:
|
|
# print "Test 1: Failed"
|
|
# print "Recieved " + str(case1)
|
|
|
|
|
|
case2 = solution(set2)
|
|
if case2 == set2Out:
|
|
print "Test 2: Passed"
|
|
else:
|
|
print "Test 2: Failed"
|
|
print "Recieved " + str(case2)
|
|
|
|
# case3 = solution(set3)
|
|
# if case3 == set3Out:
|
|
# print "Test 3: Passed"
|
|
# else:
|
|
# print "Test 3: Failed"
|
|
# print "Recieved " + str(case3)
|
|
|
|
|
|
def print2D(array):
|
|
for arr in array:
|
|
print arr
|
|
return "" |