-
Notifications
You must be signed in to change notification settings - Fork 0
/
matrix.py
149 lines (135 loc) · 6.15 KB
/
matrix.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import types
import collections
from Fraction import Fraction
from Fraction import AutoReduceFraction
from Vector import Vector
from queue import PriorityQueue
#This assumes a 2d matrix
#should change to a tuple??
class Matrix:
def __init__(self, rowList):
if (not Matrix.couldFormMatrix(rowList)):
raise ValueError("Invalid parameters for matrix: " + str(rowList))
self.rows = rowList
def isSquare(self):
return len(self.rows)==len(self.rows[0]) #only testing 1st row b/c all rows have to have same len
#look @ replibr?
def __str__(self):
ret = "START of matrix\n"
for row in self.rows:
ret += str(row)+"\n"
return ret + "END OF MATRIX"
@staticmethod
def couldFormMatrix(vectorList):
"""If not a list of Vectors that are all the same dimension, it will return false"""
return all(x.getDimension() == vectorList[0].getDimension() for x in vectorList) # Right now, only check is if they have the same dimensino
def canAddWith(self,otherMatrix):
return isinstance(otherMatrix,Matrix) and self.getDim()==otherMatrix.getDim()
def canMultWith(self,otherMatrix):
return isinstance(otherMatrix,Matrix) and self.getColNum()==otherMatrix.getRowNum()
def getRowNum(self):
return len(self.rows)
def getColNum(self):
return self.rows[0].getDimension()
def getDim(self):
return (self.getRowNum(),self.getColNum())
def getCol(self,col): #cache later?
colContents = []
for row in self.rows:
colContents.append(row[col])
return Vector(colContents)
def getRow(self,row):
return self.rows[row]
def __add__(self,otherMatrix):
if not self.canAddWith(otherMatrix): raise ValueError("Cannot add " + str(otherMatrix))
newVecRows = [x+y for (x,y) in zip(self.rows,otherMatrix.rows)]
return Matrix(newVecRows)
def __mul__(self,otherMatrix): #TODO: Threre is a more efficeint way to multiply!
if not self.canMultWith(otherMatrix): raise ValueError("Cannot mult with " + str(otherMatrix))
newVecs = []
for row in self.rows:
newRow = []
for cNum in range(0,otherMatrix.getColNum()):
newRow.append(row.dot(otherMatrix.getCol(cNum)))
newVecs.append(Vector(newRow))
return Matrix(newVecs)
def __eq__(self, otherMatrix):
if not isinstance(otherMatrix, Matrix): return False
for pair in zip(self.rows, otherMatrix.rows):
if not pair[0] == pair[1]: return False
return True
def __getitem__(self,key):
return self.getRow(key)
#returns a Reduced Echelon Form of this matrix
def getREF(self):
#used to make sure that each each vector in priority queue is a unique instance
#Using a tuple to make priorities in the queue b/c there are too
#many ways to naturally sort vectors and subclassing seemed like overkill
#First tiebreaker is the pivot location
#Next tiebreaker is "qId" which is basically the order it entered the queue
def nextQId():
nextQId.id = nextQId.id+1
return nextQId.id
nextQId.id = 0
#These methods have to do with the PriorityQueue
#The first converts the vector to a tuple so that the priority queue can sort by the pivot
#The second converts from this tuple back to vector form
def qForm(vec):
if vec.firstNonZeroLoc() is not None:
return (vec.firstNonZeroLoc(),nextQId(),vec)
else:
return vec.getDimension()+1,nextQId(),vec
def vecForm(tup):
return tup[2]
q = PriorityQueue()
for row in self.rows:
q.put_nowait(qForm(row))
finishedVecs = []
while not q.empty():
topVec = vecForm(q.get_nowait())
if q.empty(): #top Vec was the last one
finishedVecs.append(topVec)
break
#can't use zero vector to subtract stuff out
#Additionally, this means all remaining vectors are zero vectors
elif topVec.firstNonZeroLoc() is None:
finishedVecs.append(topVec)
else:
nextVec = vecForm(q.get_nowait())
#While there are vectors w/ same pivot, subtract them
while nextVec is not None and nextVec.firstNonZeroLoc() == topVec.firstNonZeroLoc():
subNextVec = nextVec - topVec*(nextVec.firstNonZeroVal()//topVec.firstNonZeroVal())
q.put_nowait(qForm(subNextVec))
nextVec = vecForm(q.get_nowait()) #Have to put in queue to make sure we don't skip any w/ same pivot
if nextVec is not None: #got out of loop b/c pivot position didn't math. There is probably a cleaner way to do this
q.put_nowait(qForm(nextVec))
finishedVecs.append(topVec)#topVec is now the only one w/ that pivot
return Matrix(finishedVecs)
#Returns the reduced row echelon form of the matrix.
def getRREF(self):
ref = self.getREF()
startWithOnes = []
for row in ref.rows:
if (row.firstNonZeroVal() is not None):
startWithOnes.append(row//row.firstNonZeroVal())
else:
startWithOnes.append(row)
#assuming that startWithOnes is in REF order
for i in range(len(startWithOnes) -1, 0, -1):
subtractor = startWithOnes[i]
firstNonZeroLoc = subtractor.firstNonZeroLoc()
if firstNonZeroLoc is not None:
for j in range(i -1, -1, -1):
startWithOnes[j] = startWithOnes[j] - subtractor * startWithOnes[j][firstNonZeroLoc]
return Matrix(startWithOnes)
@staticmethod
def identityMatrix(size):
if size <= 0:
raise ValueError("size must be at least 1. Was "+str(size))
vecs = []
for pos in range (0, size):
vecs.append(Vector([0]*pos + [1] + [0]*(size-pos -1)))
return Matrix(vecs)
#subTestMat = Matrix([one,two])
#print(subTestMat)
#print(subTestMat[0][0])