Matriz permutación
Introducción
Una matriz permutación es una matriz cuadrada con todos sus elementos iguales a 0, excepto uno cualquiera por cada fila y columna, el cual debe ser igual a 1.
Ejercicio
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
-- En este ejercicio se usará el tipo de las matrices definido por -- type Matriz a = Array (Int,Int) a -- y los siguientes ejemplos de matrices -- q1, q2, q3 :: Matriz Int -- q1 = array ((1,1),(2,2)) [((1,1),1),((1,2),0),((2,1),0),((2,2),1)] -- q2 = array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),0),((2,2),1)] -- q3 = array ((1,1),(2,2)) [((1,1),3),((1,2),0),((2,1),0),((2,2),1)] -- -- Definir la función -- esMatrizPermutacion :: Num a => Matriz a -> Bool -- tal que (esMatrizPermutacion p) se verifica si p es una matriz -- permutación. Por ejemplo. -- 1esMatrizPermutacion q1 == True -- esMatrizPermutacion q2 == False -- esMatrizPermutacion q3 == False |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import Data.Array type Matriz a = Array (Int,Int) a q1, q2, q3 :: Matriz Int q1 = array ((1,1),(2,2)) [((1,1),1),((1,2),0),((2,1),0),((2,2),1)] q2 = array ((1,1),(2,2)) [((1,1),0),((1,2),1),((2,1),0),((2,2),1)] q3 = array ((1,1),(2,2)) [((1,1),3),((1,2),0),((2,1),0),((2,2),1)] esMatrizPermutacion :: (Num a, Eq a) => Matriz a -> Bool esMatrizPermutacion p = and [esListaUnitaria [p!(i,j) | i <- [1..n]] | j <- [1..n]] && and [esListaUnitaria [p!(i,j) | j <- [1..n]] | i <- [1..n]] where (_,(n,_)) = bounds p -- (esListaUnitaria xs) se verifica si xs tiene un 1 y los restantes -- elementos son 0. Por ejemplo, -- esListaUnitaria [0,1,0,0] == True -- esListaUnitaria [0,1,0,1] == False -- esListaUnitaria [0,2,0,0] == False esListaUnitaria :: (Num a, Eq a) => [a] -> Bool esListaUnitaria xs = [x | x <- xs, x /= 0] == [1] |