lib.py

"""
Created on Mon Feb 26 14:29:11 2018

@author: Christian Bender
@license: MIT-license

This module contains some useful classes and functions for dealing
with linear algebra in python.

Overview:

- class Vector
- function zero_vector(dimension)
- function unit_basis_vector(dimension, pos)
- function axpy(scalar, vector1, vector2)
- function random_vector(N, a, b)
- class Matrix
- function square_zero_matrix(N)
- function random_matrix(W, H, a, b)
"""

from __future__ importannotations

importmath
importrandom
fromcollections.abcimportCollection
fromtypingimportoverload


classVector:
"""
 This class represents a vector of arbitrary size.
 You need to give the vector components.

 Overview of the methods:

 __init__(components: Collection[float] | None): init the vector
 __len__(): gets the size of the vector (number of components)
 __str__(): returns a string representation
 __add__(other: Vector): vector addition
 __sub__(other: Vector): vector subtraction
 __mul__(other: float): scalar multiplication
 __mul__(other: Vector): dot product
 copy(): copies this vector and returns it
 component(i): gets the i-th component (0-indexed)
 change_component(pos: int, value: float): changes specified component
 euclidean_length(): returns the euclidean length of the vector
 angle(other: Vector, deg: bool): returns the angle between two vectors
 """

def__init__(self, components: Collection[float] |None=None) ->None:
"""
 input: components or nothing
 simple constructor for init the vector
 """
ifcomponentsisNone:
components= []
self.__components=list(components)

def__len__(self) ->int:
"""
 returns the size of the vector
 """
returnlen(self.__components)

def__str__(self) ->str:
"""
 returns a string representation of the vector
 """
return"("+",".join(map(str, self.__components)) +")"

def__add__(self, other: Vector) ->Vector:
"""
 input: other vector
 assumes: other vector has the same size
 returns a new vector that represents the sum.
 """
size=len(self)
ifsize==len(other):
result= [self.__components[i] +other.component(i) foriinrange(size)]
returnVector(result)
else:
raiseException("must have the same size")

def__sub__(self, other: Vector) ->Vector:
"""
 input: other vector
 assumes: other vector has the same size
 returns a new vector that represents the difference.
 """
size=len(self)
ifsize==len(other):
result= [self.__components[i] -other.component(i) foriinrange(size)]
returnVector(result)
else: # error case
raiseException("must have the same size")

def__eq__(self, other: object) ->bool:
"""
 performs the comparison between two vectors
 """
ifnotisinstance(other, Vector):
returnNotImplemented
iflen(self) !=len(other):
returnFalse
returnall(self.component(i) ==other.component(i) foriinrange(len(self)))

@overload
def__mul__(self, other: float) ->Vector: ...

@overload
def__mul__(self, other: Vector) ->float: ...

def__mul__(self, other: float|Vector) ->float|Vector:
"""
 mul implements the scalar multiplication
 and the dot-product
 """
ifisinstance(other, (float, int)):
ans= [c*otherforcinself.__components]
returnVector(ans)
elifisinstance(other, Vector) andlen(self) ==len(other):
size=len(self)
prods= [self.__components[i] *other.component(i) foriinrange(size)]
returnsum(prods)
else: # error case
raiseException("invalid operand!")

defcopy(self) ->Vector:
"""
 copies this vector and returns it.
 """
returnVector(self.__components)

defcomponent(self, i: int) ->float:
"""
 input: index (0-indexed)
 output: the i-th component of the vector.
 """
ifisinstance(i, int) and-len(self.__components) <=i<len(self.__components):
returnself.__components[i]
else:
raiseException("index out of range")

defchange_component(self, pos: int, value: float) ->None:
"""
 input: an index (pos) and a value
 changes the specified component (pos) with the
 'value'
 """
# precondition
assert-len(self.__components) <=pos<len(self.__components)
self.__components[pos] =value

defeuclidean_length(self) ->float:
"""
 returns the euclidean length of the vector

 >>> Vector([2, 3, 4]).euclidean_length()
 5.385164807134504
 >>> Vector([1]).euclidean_length()
 1.0
 >>> Vector([0, -1, -2, -3, 4, 5, 6]).euclidean_length()
 9.539392014169456
 >>> Vector([]).euclidean_length()
 Traceback (most recent call last):
 ...
 Exception: Vector is empty
 """
iflen(self.__components) ==0:
raiseException("Vector is empty")
squares= [c**2forcinself.__components]
returnmath.sqrt(sum(squares))

defangle(self, other: Vector, deg: bool=False) ->float:
"""
 find angle between two Vector (self, Vector)

 >>> Vector([3, 4, -1]).angle(Vector([2, -1, 1]))
 1.4906464636572374
 >>> Vector([3, 4, -1]).angle(Vector([2, -1, 1]), deg = True)
 85.40775111366095
 >>> Vector([3, 4, -1]).angle(Vector([2, -1]))
 Traceback (most recent call last):
 ...
 Exception: invalid operand!
 """
num=self*other
den=self.euclidean_length() *other.euclidean_length()
ifdeg:
returnmath.degrees(math.acos(num/den))
else:
returnmath.acos(num/den)


defzero_vector(dimension: int) ->Vector:
"""
 returns a zero-vector of size 'dimension'
 """
# precondition
assertisinstance(dimension, int)
returnVector([0] *dimension)


defunit_basis_vector(dimension: int, pos: int) ->Vector:
"""
 returns a unit basis vector with a One
 at index 'pos' (indexing at 0)
 """
# precondition
assertisinstance(dimension, int)
assertisinstance(pos, int)
ans= [0] *dimension
ans[pos] =1
returnVector(ans)


defaxpy(scalar: float, x: Vector, y: Vector) ->Vector:
"""
 input: a 'scalar' and two vectors 'x' and 'y'
 output: a vector
 computes the axpy operation
 """
# precondition
assertisinstance(x, Vector)
assertisinstance(y, Vector)
assertisinstance(scalar, (int, float))
returnx*scalar+y


defrandom_vector(n: int, a: int, b: int) ->Vector:
"""
 input: size (N) of the vector.
 random range (a,b)
 output: returns a random vector of size N, with
 random integer components between 'a' and 'b'.
 """
random.seed(None)
ans= [random.randint(a, b) for_inrange(n)]
returnVector(ans)


classMatrix:
"""
 class: Matrix
 This class represents an arbitrary matrix.

 Overview of the methods:

 __init__():
 __str__(): returns a string representation
 __add__(other: Matrix): matrix addition
 __sub__(other: Matrix): matrix subtraction
 __mul__(other: float): scalar multiplication
 __mul__(other: Vector): vector multiplication
 height() : returns height
 width() : returns width
 component(x: int, y: int): returns specified component
 change_component(x: int, y: int, value: float): changes specified component
 minor(x: int, y: int): returns minor along (x, y)
 cofactor(x: int, y: int): returns cofactor along (x, y)
 determinant() : returns determinant
 """

def__init__(self, matrix: list[list[float]], w: int, h: int) ->None:
"""
 simple constructor for initializing the matrix with components.
 """
self.__matrix=matrix
self.__width=w
self.__height=h

def__str__(self) ->str:
"""
 returns a string representation of this matrix.
 """
ans=""
foriinrange(self.__height):
ans+="|"
forjinrange(self.__width):
ifj<self.__width-1:
ans+=str(self.__matrix[i][j]) +","
else:
ans+=str(self.__matrix[i][j]) +"|\n"
returnans

def__add__(self, other: Matrix) ->Matrix:
"""
 implements matrix addition.
 """
ifself.__width==other.width() andself.__height==other.height():
matrix= []
foriinrange(self.__height):
row= [
self.__matrix[i][j] +other.component(i, j)
forjinrange(self.__width)
 ]
matrix.append(row)
returnMatrix(matrix, self.__width, self.__height)
else:
raiseException("matrix must have the same dimension!")

def__sub__(self, other: Matrix) ->Matrix:
"""
 implements matrix subtraction.
 """
ifself.__width==other.width() andself.__height==other.height():
matrix= []
foriinrange(self.__height):
row= [
self.__matrix[i][j] -other.component(i, j)
forjinrange(self.__width)
 ]
matrix.append(row)
returnMatrix(matrix, self.__width, self.__height)
else:
raiseException("matrices must have the same dimension!")

@overload
def__mul__(self, other: float) ->Matrix: ...

@overload
def__mul__(self, other: Vector) ->Vector: ...

def__mul__(self, other: float|Vector) ->Vector|Matrix:
"""
 implements the matrix-vector multiplication.
 implements the matrix-scalar multiplication
 """
ifisinstance(other, Vector): # matrix-vector
iflen(other) ==self.__width:
ans=zero_vector(self.__height)
foriinrange(self.__height):
prods= [
self.__matrix[i][j] *other.component(j)
forjinrange(self.__width)
 ]
ans.change_component(i, sum(prods))
returnans
else:
raiseException(
"vector must have the same size as the "
"number of columns of the matrix!"
 )
elifisinstance(other, (int, float)): # matrix-scalar
matrix= [
 [self.__matrix[i][j] *otherforjinrange(self.__width)]
foriinrange(self.__height)
 ]
returnMatrix(matrix, self.__width, self.__height)
returnNone

defheight(self) ->int:
"""
 getter for the height
 """
returnself.__height

defwidth(self) ->int:
"""
 getter for the width
 """
returnself.__width

defcomponent(self, x: int, y: int) ->float:
"""
 returns the specified (x,y) component
 """
if0<=x<self.__heightand0<=y<self.__width:
returnself.__matrix[x][y]
else:
raiseException("change_component: indices out of bounds")

defchange_component(self, x: int, y: int, value: float) ->None:
"""
 changes the x-y component of this matrix
 """
if0<=x<self.__heightand0<=y<self.__width:
self.__matrix[x][y] =value
else:
raiseException("change_component: indices out of bounds")

defminor(self, x: int, y: int) ->float:
"""
 returns the minor along (x, y)
 """
ifself.__height!=self.__width:
raiseException("Matrix is not square")
minor=self.__matrix[:x] +self.__matrix[x+1 :]
foriinrange(len(minor)):
minor[i] =minor[i][:y] +minor[i][y+1 :]
returnMatrix(minor, self.__width-1, self.__height-1).determinant()

defcofactor(self, x: int, y: int) ->float:
"""
 returns the cofactor (signed minor) along (x, y)
 """
ifself.__height!=self.__width:
raiseException("Matrix is not square")
if0<=x<self.__heightand0<=y<self.__width:
return (-1) ** (x+y) *self.minor(x, y)
else:
raiseException("Indices out of bounds")

defdeterminant(self) ->float:
"""
 returns the determinant of an nxn matrix using Laplace expansion
 """
ifself.__height!=self.__width:
raiseException("Matrix is not square")
ifself.__height<1:
raiseException("Matrix has no element")
elifself.__height==1:
returnself.__matrix[0][0]
elifself.__height==2:
return (
self.__matrix[0][0] *self.__matrix[1][1]
-self.__matrix[0][1] *self.__matrix[1][0]
 )
else:
cofactor_prods= [
self.__matrix[0][y] *self.cofactor(0, y) foryinrange(self.__width)
 ]
returnsum(cofactor_prods)


defsquare_zero_matrix(n: int) ->Matrix:
"""
 returns a square zero-matrix of dimension NxN
 """
ans: list[list[float]] = [[0] *nfor_inrange(n)]
returnMatrix(ans, n, n)


defrandom_matrix(width: int, height: int, a: int, b: int) ->Matrix:
"""
 returns a random matrix WxH with integer components
 between 'a' and 'b'
 """
random.seed(None)
matrix: list[list[float]] = [
 [random.randint(a, b) for_inrange(width)] for_inrange(height)
 ]
returnMatrix(matrix, width, height)