TP IPT 7 : la matrice...

#!/usr/bin/python3
#-*- coding: utf-8 -*-
 
#from functools import reduce
from operator  import mul, floordiv, truediv,add
from random    import randint, random
from math      import log,ceil
#from fractions import Fraction
import numpy as np
from scipy import misc, linalg
from matplotlib import cm
from pylab import imshow
#from sympy import randMatrix
from math import floor, sqrt
import matplotlib.pyplot as plt
from urllib.request import urlretrieve
 
#from subprocess import call
 
 
 
class Mat:
    """ une matrice sous la forme Mat([nb lignes, nb cols], fonction(i,j))"""
 
    def __init__(self, dim, f):
        self.F = f   # fonction (i,j) -> coeff en position i,j
        self.D = dim # liste [nb de lignes, nb de cols]
 
    def ligne(self,i):
        return None # à compléter
 
    def col(self,j):
        return None # à compléter
 
    def indices(self):
        [r,c] = self.D
        for i in range(r):
            for j in range(c):
                yield (i,j)
 
    def __getitem__(self,cle):
        """ permet d'obtenir Mij avec M[i,j]"""
        return self.F(*cle)
        
    def __iter__(self):
        """ pour itérer sur la liste des coefficients """ 
        [r,c] = self.D
        for j in range(c):
            for i in range(r):
                yield self.F(i,j)
        
    def __str__(self):
        """ joli affichage d'une matrice"""
        [r,c],f = self.D, self.F
        lmax = len(str(max(iter(self)))) + 1
        s = '\n'.join( (' '.join('{0:{l}G}'.format(f(i,j),l=lmax) if isinstance(f(i,j), int) or isinstance(f(i,j), float) else str(f(i,j)) for j in range(c))) for i in range(r))
        return s
 
    def __repr__(self):
        """ représentation dans le REPL"""
        return str(self)
  
    def __neg__(self):
        """ opposé d'une matrice : utilisation du symbole -"""
        return None # à compléter
           
    def __add__(self,other):
        """ somme de deux matrices : utilisation du symbole +"""
        assert self.D == other.D, "tailles incompatibles"
        return Mat(self.D, lambda i,j : self.F(i,j) + other.F(i,j))
 
    def __sub__(self,other):
        """ différence de deux matrices : utilisation dyu symbole -"""
        return None # à compléter
 
    def transpose(self):
        """ transposée d'une matrice """
        return None # à compléter
 
    def prod_par_scal(self,k):
        """ renvoie le produit d'une matrice par un scalaire"""
        return None # à compléter
 
    def prod_mat(self,other):
        """ renvoie le produit de deux matrices"""
        return None # à compléter
        
    def map(self,f):
        return Mat(self.D, lambda i,j: f(self.F(i,j)))
 
    def __mul__(self,other):
        """ produit d'une matrice par un scalaire ou une matrice : utilisation du symbole *"""
        if Mat == type(other):
            return self.prod_mat(other)
        else:
            return self.prod_par_scal(other)
 
 
    def powr(self,n):
        """ expo rapide : version récursive"""
        r = self.D[0]
        if n == 0:
            return unite(r)
        def pui(m,k,acc):
            if k == 0:
                return acc
            return pui((m*m),k//2,acc if k % 2 == 0 else (m*acc))
        return pui(self,n,unite(r))
 
    def __pow__(self,n):
        """expo rapide version impérative"""
        return None # à compléter
    
    def __eq__(self,other):
        """test d'égalité de deux matrices"""
        if (self.D != other.D):
            return False
        f,g = self.F, other.F
        for (i,j) in self.indices():
            if f(i,j) != g(i,j):
                return False
        return True
 
    
    def trace(self):
        return None # à compléter
 
 
    def comb_lignes(self,ki,kj,i,j):
        """Li <- ki*Li + kj * Lj"""
        f = self.F
        g = lambda r,c : ki*f(i,c) + kj*f(j,c) if r == i else f(r,c)
        return Mat(self.D,g)
 
    def mult_ligne(self,k,i):
        """Li <- k*Li"""
        return None # à compléter
 
    def cat_carre_droite(self):
        """
        Colle l'identité à droite pour la méthode de GJ
 
        """
        return None # à compléter
        
    def extrait_carre_droite(self):
        """
        Extrait le carré de droite d'un tableau de GJ
 
        """
        return None # à compléter
 
    def swap(self,i,j):
        """
        Li <-> Lj
        """
        return None # à compléter
 
    def decoupe(self):
        """
        Fonction interne à triangle qui  retire la 1ère ligne et la 1ère colonne
 
        """
        [lig, col], f = self.D, self.F
        return Mat([lig-1,col-1],lambda r,c : f(r+1,c+1))
 
    def decoupe_bas(self):
        """
        Fonction interne à diago_triangle qui retire la dernière ligne et la
        colonne de même numéro de S
 
        """
        [lig, col], f = self.D, self.F
        #g = lambda r,c: f(lig-1,c) if r == lig else f(i,c) if r == lig-1 else f(r,c)
        g = lambda r,c: f(r,c) if c < lig - 1 else f(r,c+1)
        return Mat([lig-1,col-1],lambda r,c : g(r,c))
 
    def remplace_ligned(self,i,g):
        """
        Fonction interne à triangle qui remplace dans la ligne i
        les coefficients à partir de la colonne i par ceux du tableau S
        """
        [lig, col], f = self.D, self.F
        h = lambda r,c: g(r-i,c-i) if r == i and c >= i else  f(r,c)
        return Mat([lig,col],h)
 
    def remplace_ligneg(self,i,g):
        """
        Fonction interne à diago_triangle qui remplace dans la ligne i
        les coefficients à partir de la colonne i par ceux du tableau S
        """
        [lig, col], f = self.D, self.F
        h = lambda r,c: g(r,c - (lig - 1) + i) if r == i and c >= i else  f(r,c)
        return Mat([lig,col],h)
 
    def triangle(self):
        """ renvoie la triangulation d'une matrice de haut en bas """
        [r,c] = self.D
        m     = min(r,c)
        S     = self
        T     = zeros(r,c)
        while m > 0:
            NoLigne = 0
            while S[NoLigne, 0] == 0 and (NoLigne < m - 1):
                    NoLigne += 1
            S = S.swap(NoLigne,0)
            if S[0, 0] != 0:
                pivot = S[0,0]
                for k in range(1,m):
                    if S[k,0] != 0:
                        S = S.comb_lignes(pivot, -S[k,0],k,0)
                        #print("pivot = "+str(pivot))
                        #print("S dans for :")
                        #print(S)
            T = T.remplace_ligned(r - m,S.F)
            #print("Évolution de T :")
            #print(T)
            S = S.decoupe()
            m -= 1
        return T
 
    def diago_triangle(self,inv):
        """ renvoie la triangulation d'un tableau de GJ d'une matrice
        inversible de bas en haut """
        return None # à compléter
 
    
 
    def rang(self):
        return None # à compléter
 
 
    def det(self,div):
        """ renvoie le déterminant de self par Gauss-Jordan """
        return None # à compléter
    
 
    def inverse(self,inv):
        return self.cat_carre_droite().triangle().diago_triangle(inv).extrait_carre_droite()
 
 
# In [340]: A = list2mat([[0,1,0,0],[2,-1,9,1],[2,7,4,-12],[2,0,-1,-1]])
    
    
def next_pow_2(x):
    return 2**(ceil(log(x)/log(2)))
 
def all(it):
    for i in it:
        if not i:
            return False
    return True
    
def randmat(r,c,min = 0,max = 9):
    return Mat([r,c],lambda  i,j : randint(min,max))
 
def list2mat(mat):
    r,c = len(mat),len(mat[0])
    return Mat([r,c], lambda i,j : mat[i][j])
 
 
def prod_scal(it1,it2):
    return None # à compléter
 
def unite(n):
    return Mat([n,n], lambda i,j: 1 if i == j else 0)
 
 
def zeros(r,c):
    return None # à compléter
 
 
 
###############
#
#  Lena
#
#################"
 
def rvb_to_gray(m):
    r = len(m)
    c = len(m[0])
    return(np.array([[m[i,j][0] for j in range(c)] for i in range(r)]))
 
def array2mat(tab):
    """ convertit un array de numpy en objet de type Mat"""
    dim = list(tab.shape)
    return Mat(dim,  lambda i,j : tab[i,j])
 
def mat2array(mat):
    """ convertir un objet de type Mat en array de numpy """
    return np.fromfunction(np.vectorize(mat.F),tuple(mat.D),dtype = int)
 
urlretrieve('http://download.tuxfamily.org/tehessinmath/les_images/lenaFace.jpeg','lenaFace.jpeg')
 
lena_face_couleur = plt.imread('./lenaFace.jpeg')
 
lena_face_array = rvb_to_gray(lena_face_couleur)
 
lena_face = array2mat(lena_face_array)
 
matlena = array2mat(misc.lena())
 
def montre(mat):
    """ permet de visualiser les images dans un terminal """
    return imshow(mat2array(mat), cmap = cm.gray)
 
 
def retourne(m):
    [r,c], f = m.D, m.F
    return None # à compléter
 
def miroir(m):
    [r,c], f = m.D, m.F
    return None # à compléter
 
def resolution(k,mat):
    [r,c],f = mat.D,mat.F
    return None # à compléter
    
 
 
def ber(p):
    return 1 if random() < p else 0
 
def rand_image(dim,p):
    return Mat(dim, lambda i,j : randint(0,255)*ber(p))
    
def bruit(mat,p):
     return (mat + rand_image(mat.D,p)).map(lambda x : x % 256)
 
def moyenne(mat,k):
    return None # à compléter
 
 
def mediane(mat,k):
    return None # à compléter
 
def contour(m):
    return None # à compléter
 
 
 
def comp_svd(mat,k):
    return None # à compléter
 
 
def c_svd(mat,k):
    return None # à compléter
        
 
#    U,s,tV = linalg.svd(mat)
#    x = np.arange(len(s))
#    plot(x,s)
 
def anim(im,n):
    for k in range(n):
        plt.imsave("lena_face_svd" + str(1000 + k), c_svd(lena_face_array,k), cmap = cm.gray)
 
# call("apngasm anim_lena_face.png lena_face_svd*.png 1 1 && firefox anim lenaface_svd.png")

#######################################
#
#        Chiffrement de Hill
#
#######################################
 
def ascii(chaine):
    return [ord(c)-ord((' ')) for c in chaine]
 
def deascii(chaine):
    return ''.join(chr(x + ord((' '))) for x in chaine)
 
def to_Hill(m,p):
   """transforme une chaîne de caractères en une matrice de code ascii de p colonnes"""
   return None # à compléter
 
cle = list2mat([[1,23,29],[0,31,1],[47,3,1]])
 
def bezout(a,b):
    """ retourne des coeffs de Bézout et le pgcd de a et b """
    return None # à compléter 
 
 
def inv_mod(p,n):
    """ retourne l'inverse de p modulo n"""
 
 
inv_cle = cle.inverse(lambda x: inv_mod(x, 95)).map(lambda n : n % 95)
 
clair = to_Hill("Arghh !! Ce 1000 pattes aurait 314 pattes ??",3)
 
crypte = deascii(iter((cle * clair).map(lambda n : n % 95)))
 
 
decrypte = deascii(???)