Определитель матрицы рекурсивно python

Вычисление определителя матрицы рекурсивно

Я пытаюсь вычислить определитель матрицы с помощью рекурсивной функции. Я получил класс Matrix с getitem, setitem. Метод.eliminated(i,j) вернет новую матрицу, в которой удалены строка i, столбец j.

Вот класс Matrix, я также создал класс Array, класс Array_2D и все они в порядке:

class Matrix: def __init__(self, numRows, numCols): self.grid = Array_2D(numRows,numCols) self.grid.clear(0) def __getitem__(self, tuple): return self.grid[tuple[0],tuple[1]] def numRows(self): return self.grid.numRows() def numCols(self): return self.grid.numCols() def __add__(self, other): assert other.numRows() == self.numRows() and\ other.numCols == self.numCols() , "Matrix sizes not compatible" newMatrix = Matrix(self.numRows(),self.numCols()) for r in range(self.numRows()): for c in range(self.numCols()): newMatrix[r,c]=self[r,c]+other[r,c] return newMatrix def __setitem__(self, tuple, value): self.grid[tuple[0],tuple[1]]=value def scaleBy(self,scalar): for r in range(self.numRows()): for c in range(self.numCols()): self[r,c]=self[r,c]*scalar def tranpose(self): newMatrix = Matrix(self.numCols(),self.numRows()) for r in range(newMatrix.numRows()): for c in range(newMatrix.numCols()): newMatrix[r,c]=self[c,r] return newMatrix def __sub__(self, other): assert other.numRows() == self.numRows() and \ other.numCols == self.numCols(), "Matrix sizes not compatible" newMatrix = Matrix(self.numRows(), self.numCols()) for r in range(self.numRows()): for c in range(self.numCols()): newMatrix[r, c] = self[r, c] - other[r, c] return newMatrix def __mul__(self, other): assert other.numRows() == self.numCols(), "Matrix sizes not compatible" newMatrix = Matrix(self.numRows(),other.numCols()) for r in range(newMatrix.numRows()): for c in range(newMatrix.numCols()): newMatrix[r,c] = 0 for i in range(self.numCols()): newMatrix[r,c]+=self[r,i]*other[i,c] return newMatrix def determinant(self): assert self.numCols()==self.numRows(), "Must be a square matrix" assert self.numCols() > 0 if self.numCols() == 1: return self[0,0] if self.numCols() == 2: return self[0,0]*self[1,1]-self[0,1]*self[1,0] det = 0 if self.numCols() >=2: for c in range(self.numCols()): det+=((-1) ** c) * self[0, c] * self.eliminated(0, c).determinant() return det def eliminated(self,row,col): assert row >=0 and row < self.numRows(), "Invalid row" assert col >=0 and col < self.numCols(), "Invalid column" assert self.numCols() >1 and self.numRows()>1 entry_list = [] for r in range(self.numRows()): for c in range(self.numCols()): self[r, col] = None self[row,c]=None if self[r,c] != None: entry_list.append(self[r,c]) new_matrix = Matrix(self.numRows()-1, self.numCols()-1) for r in range(new_matrix.numRows()): for c in range(new_matrix.numCols()): new_matrix[r,c] = entry_list[c + r*new_matrix.numCols()] return new_matrix 

Я продолжал получать эту ошибку для матрицы 3х3, 2х2 и 1х1 в порядке:

Traceback (most recent call last): File "E:/DataStructures/matrix.py", line 100, in print(ma4.determinant()) File "E:/DataStructures/matrix.py", line 67, in determinant det+=((-1) ** c) * self[0, c] * self.eliminated(0, c).determinant() TypeError: unsupported operand type(s) for *: 'int' and 'NoneType' 

Я знаю, что моя рекурсивная функция продолжает удалять строки и столбцы, пока не доберется до NoneType, но не знаю, как это исправить

1 ответ

Здравствуйте, проверьте это:

matrix=[] def det(IC,i): global matrix,row determinent=0 m=1 for j in range(len(matrix)): if j not in IC: m+=1 if i == row-1: determinent = matrix[i][j] else: determinent+=(-1)**(m)*matrix[i][j]*det(IC+[j],i+1) return determinent row=int(input("enter order:")) for i in range(row): rowEntry=[int(x) for x in input().split(' ')] matrix.append(rowEntry) print(matrix) print(det([],0)) 

Пожалуйста, дайте вход тщательно, например: введите заказ: 3

Источник

Рекурсивный определитель на языке Python

Я сделал рекурсивную функцию для вычисления детерминанта матрицы на основе кофакторов:

# determinant of a 2x2 matrix def det2(matrix): return matrix[0][0]*matrix[1][1]-matrix[1][0]*matrix[0][1] # recursive part def recursion(matrix,somme=None,prod=1): if(somme==None): somme=[] if(len(matrix)==1): somme.append(matrix[0][0]) elif(len(matrix)==2): somme.append(det2(matrix)*prod) else: for index, elmt in enumerate(matrix[0]): transposee = [list(a) for a in zip(*matrix[1:])] transposee.remove(transposee[index]) mineur = [list(a) for a in zip(*transposee)] somme = recursion(mineur,somme,prod*matrix[0][index]*(-1)**(index+2)) return somme def main(matrix): return sum(recursion(matrix)) 

Ничего сложного, кроме того, что я не понимаю, почему это не работает. В некоторых случаях он дает правильный ответ, но не все. Я подозреваю, что результат неправильный, когда в матрице 0s, но я не уверен.

Я думаю, что ваша проблема, вероятно, здесь:

transposee.remove(transposee[index]) 

remove удаляет первое вхождение значения, переданного ему из list . Ваша тестовая матрица имеет несколько повторяющихся значений, и поэтому удаленный может не быть тем, который вы хотите удалить, чтобы создать массив mineur .

Ваш алгоритм работает для случайных массивов, потому что подобные дубликаты вряд ли произойдут в этом случае.

Чтобы ваша программа работала, замените строку на

который будет конкретно удалять значение по index .

Источник

вычисление определителя матрицы (nxn) рекурсивно

Я собираюсь написать код, который вычисляет определитель квадратной матрицы (nxn), используя алгоритм Лапласа (значение рекурсивного алгоритма), как написано Википедия Расширение Лапласа. У меня уже есть класс Matrix , который включает init, setitem, getitem, repr и все, что мне нужно для вычисления детерминанта (включая minor(i,j) ). Итак, я пробовал код ниже:

def determinant(self,i=0) # i can be any of the matrix rows assert isinstance(self,Matrix) n,m = self.dim() # Q.dim() returns the size of the matrix Q assert n == m if (n,m) == (1,1): return self[0,0] det = 0 for j in range(n): det += ((-1)**(i+j))*(self[i,j])*((self.minor(i,j)).determinant()) return det 

Как и ожидалось, при каждом рекурсивном вызове self превращается в подходящего несовершеннолетнего. Но, возвращаясь из рекурсивного вызова, он не возвращается к исходной матрице. Это вызывает проблемы, когда в цикле for (когда функция прибывает в (n,m)==(1,1) , возвращается это одно значение матрицы, но в цикле for self все еще является матрицей 1×1 — почему?)

Я бы посоветовал не использовать assert s, как это. Первый ( assert isinstance(self, Matrix) ) ничего не делает — это метод в Matrix , так что вы точно знаете, что self — это Matrix . Второй будет лучше работать с чем-то вроде, if n != m: raise ValueError(«Matrix is not square») потому что исключение более конкретно относится к проблеме (и может быть поймано легче).

Кроме того, вы действительно хотите, чтобы пользователь мог передать i в качестве параметра? Определитель — это свойство матрицы, независимо от того, какую строку или столбец вы берете с собой. Так что не имеет смысла позволять пользователю выбирать (так как результат будет одинаковым, независимо от того, что он выберет).

4 ответа

Вы уверены, что ваш minor возвращает новый объект, а не ссылку на ваш исходный объект матрицы? Я использовал ваш точный метод детерминант и реализовал метод minor для вашего класса, и он отлично подходит для меня.

Ниже приведена кратковременная реализация вашего матричного класса, так как у меня нет вашей реализации. Для краткости я решил реализовать его только для квадратных матриц, что в данном случае не имеет значения, поскольку мы имеем дело с детерминантами. Обратите внимание на метод det , который совпадает с вашим, и метод minor (остальные методы предназначены для облегчения внедрения и тестирования):

class matrix: def __init__(self, n): self.data = [0.0 for i in range(n*n)] self.dim = n @classmethod def rand(self, n): import random a = matrix(n) for i in range(n): for j in range(n): a[i,j] = random.random() return a @classmethod def eye(self, n): a = matrix(n) for i in range(n): a[i,i] = 1.0 return a def __repr__(self): n = self.dim for i in range(n): print str(self.data[i*n: i*n+n]) return '' def __getitem__(self,(i,j)): assert i < self.dim and j < self.dim return self.data[self.dim*i + j] def __setitem__(self, (i, j), val): assert i < self.dim and j < self.dim self.data[self.dim*i + j] = float(val) # def minor(self, i,j): n = self.dim assert i < n and j < n a = matrix(self.dim-1) for k in range(n): for l in range(n): if k == i or l == j: continue if k < i: K = k else: K = k-1 if l < j: L = l else: L = l-1 a[K,L] = self[k,l] return a def det(self, i=0): n = self.dim if n == 1: return self[0,0] d = 0 for j in range(n): d += ((-1)**(i+j))*(self[i,j])*((self.minor(i,j)).det()) return d def __mul__(self, v): n = self.dim a = matrix(n) for i in range(n): for j in range(n): a[i,j] = v * self[i,j] return a __rmul__ = __mul__ 

import numpy as np a = matrix(3) # same matrix from the Wikipedia page a[0,0] = 1 a[0,1] = 2 a[0,2] = 3 a[1,0] = 4 a[1,1] = 5 a[1,2] = 6 a[2,0] = 7 a[2,1] = 8 a[2,2] = 9 a.det() # returns 0.0 # trying with numpy the same matrix A = np.array(a.data).reshape([3,3]) print np.linalg.det(A) # returns -9.51619735393e-16 

Остаток в случае numpy заключается в том, что он вычисляет детерминант методом (Гаусса), а не расширением Лапласа. Вы также можете сравнить результаты на случайных матрицах, чтобы увидеть, что разница между вашей детерминантной функцией и numpy не превышает точность float :

import numpy as np a = 10*matrix.rand(4) A = np.array( a.data ).reshape([4,4]) print (np.linalg.det(A) - a.det())/a.det() # varies between zero and 1e-14 

Источник

вычисление определителя матрицы (nxn) рекурсивно

Я собираюсь написать код, который вычисляет определитель квадратной матрицы (nxn), используя алгоритм Лапласа (имеется в виду рекурсивный алгоритм), как написано Википедия Расширение Лапласа.

У меня уже есть класс Matrix , который включает в себя init, setitem, getitem, repr и все то, что мне нужно для вычисления определителя (включая minor(i,j) ).

Поэтому я пробовал код ниже:

def determinant(self,i=0) # i can be any of the matrix's rows assert isinstance(self,Matrix) n,m = self.dim() # Q.dim() returns the size of the matrix Q assert n == m if (n,m) == (1,1): return self[0,0] det = 0 for j in range(n): det += ((-1)**(i+j))*(self[i,j])*((self.minor(i,j)).determinant()) return det 

Как и ожидалось, в каждом рекурсивном вызове self превращается в соответствующий минор. Но при возврате из рекурсивного вызова он не возвращается к исходной матрице. Это вызывает проблемы, когда в цикле for (когда функция достигает (n,m)==(1,1) , это единственное значение матрицы возвращается, но в цикле for self все еще матрица 1х1 - зачем?)

Я бы не советовал использовать assert таким образом. Первый ( assert isinstance(self, Matrix) ) ничего не делает — это метод для Matrix , поэтому вы точно знаете, что self — это Matrix . Второй будет лучше работать с чем-то вроде if n != m: raise ValueError("Matrix is not square") , потому что исключение более конкретно описывает проблему (и его легче поймать).

Кроме того, вы действительно хотите, чтобы пользователь мог передать i в качестве параметра? Определитель — это свойство матрицы, не зависящее от того, какую строку или столбец вы берете с собой. Так что на самом деле не имеет смысла позволять пользователю выбирать (поскольку результат будет одинаковым независимо от того, что он выберет).

5 ответов

Примечание. Я использовал одномерный список для размещения матрицы, а массив размеров — это количество строк или столбцов в квадратном массиве. Он использует рекурсивный алгоритм для нахождения определителя.

def solve(matrix,size): c = [] d = 0 print_matrix(matrix,size) if size == 0: for i in range(len(matrix)): d = d + matrix[i] return d elif len(matrix) == 4: c = (matrix[0] * matrix[3]) - (matrix[1] * matrix[2]) print(c) return c else: for j in range(size): new_matrix = [] for i in range(size*size): if i % size != j and i > = size: new_matrix.append(matrix[i]) c.append(solve(new_matrix,size-1) * matrix[j] * ((-1)**(j+2))) d = solve(c,0) return d 

Вы уверены, что ваш minor возвращает новый объект, а не ссылку на исходный матричный объект? Я использовал ваш точный метод детерминанта и реализовал метод minor для вашего класса, и он отлично работает для меня.

Ниже приведена быстрая/грязная реализация вашего матричного класса, поскольку у меня нет вашей реализации. Для краткости я решил реализовать его только для квадратных матриц, что в данном случае не должно иметь значения, поскольку мы имеем дело с определителями. Обратите внимание на метод det , такой же, как у вас, и метод minor (остальные методы предназначены для облегчения реализации и тестирования):

class matrix: def __init__(self, n): self.data = [0.0 for i in range(n*n)] self.dim = n @classmethod def rand(self, n): import random a = matrix(n) for i in range(n): for j in range(n): a[i,j] = random.random() return a @classmethod def eye(self, n): a = matrix(n) for i in range(n): a[i,i] = 1.0 return a def __repr__(self): n = self.dim for i in range(n): print str(self.data[i*n: i*n+n]) return '' def __getitem__(self,(i,j)): assert i < self.dim and j < self.dim return self.data[self.dim*i + j] def __setitem__(self, (i, j), val): assert i < self.dim and j < self.dim self.data[self.dim*i + j] = float(val) # def minor(self, i,j): n = self.dim assert i < n and j < n a = matrix(self.dim-1) for k in range(n): for l in range(n): if k == i or l == j: continue if k < i: K = k else: K = k-1 if l < j: L = l else: L = l-1 a[K,L] = self[k,l] return a def det(self, i=0): n = self.dim if n == 1: return self[0,0] d = 0 for j in range(n): d += ((-1)**(i+j))*(self[i,j])*((self.minor(i,j)).det()) return d def __mul__(self, v): n = self.dim a = matrix(n) for i in range(n): for j in range(n): a[i,j] = v * self[i,j] return a __rmul__ = __mul__ 

import numpy as np a = matrix(3) # same matrix from the Wikipedia page a[0,0] = 1 a[0,1] = 2 a[0,2] = 3 a[1,0] = 4 a[1,1] = 5 a[1,2] = 6 a[2,0] = 7 a[2,1] = 8 a[2,2] = 9 a.det() # returns 0.0 # trying with numpy the same matrix A = np.array(a.data).reshape([3,3]) print np.linalg.det(A) # returns -9.51619735393e-16 

Остаток в случае numpy связан с тем, что он вычисляет определитель с помощью метода (гауссовского) исключения, а не расширения Лапласа. Вы также можете сравнить результаты на случайных матрицах, чтобы увидеть, что разница между вашей детерминантной функцией и функцией numpy не выходит за пределы точности float :

import numpy as np a = 10*matrix.rand(4) A = np.array( a.data ).reshape([4,4]) print (np.linalg.det(A) - a.det())/a.det() # varies between zero and 1e-14 

Источник