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

-- 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

-- 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

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]

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]

3 Comentarios

esMatrizPermutacion p = 
    and [columna b p | b <- [1..numColumnas p]] && 
    and [fila a p | a<- [1..numFilas p]] 

columna b p = length [c | ((a,j),c) <- assocs p, b == j , c == 1] == 1

fila a p = length [c | ((i,b),c) <- assocs p, i == a, c == 1] == 1

numFilas p = fst (snd (bounds p))

numColumnas p = snd (snd (bounds p))

esMatrizPermutacion p =

and [columna b p | b <- [1..numColumnas p]] &&

and [fila a p | a<- [1..numFilas p]]

columna b p = length [c | ((a,j),c) <- assocs p, b == j , c == 1] == 1

fila a p = length [c | ((i,b),c) <- assocs p, i == a, c == 1] == 1

numFilas p = fst (snd (bounds p))

numColumnas p = snd (snd (bounds p))

Responder

La definición no es correcta. Por ejemplo,

ghci> esMatrizPermutacion (array ((1,1),(2,2)) [((1,1),1),((1,2),3),((2,1),0),((2,2),1)])
True

1 2	ghci> esMatrizPermutacion (array ((1,1),(2,2)) [((1,1),1),((1,2),3),((2,1),0),((2,2),1)]) True

y su valor debe de ser False.

Responder

Corrección:

esMatrizPermutacion p = 
    and [columna1 b p | b <- [1..numColumnas p]] && 
    and [fila1 a p | a <- [1..numFilas p]] 

columna1 b p = 
    length [c | ((a,j),c) <- assocs p, b == j, c /=0 ] == 1 && 
    all (==1) [c | ((a,j),c) <- assocs p, b == j, c /= 0]

fila1 a p = 
    length [c | ((i,b),c) <- assocs p, i == a, c /= 0]== 1 && 
    all (==1) [c | ((i,b),c) <- assocs p, i == a, c /= 0]

numFilas p = fst (snd (bounds p))

numColumnas p = snd (snd (bounds p))

esMatrizPermutacion p =

and [columna1 b p | b <- [1..numColumnas p]] &&

and [fila1 a p | a <- [1..numFilas p]]

columna1 b p =

length [c | ((a,j),c) <- assocs p, b == j, c /=0 ] == 1 &&

all (==1) [c | ((a,j),c) <- assocs p, b == j, c /= 0]

fila1 a p =

length [c | ((i,b),c) <- assocs p, i == a, c /= 0]== 1 &&

all (==1) [c | ((i,b),c) <- assocs p, i == a, c /= 0]

numFilas p = fst (snd (bounds p))

numColumnas p = snd (snd (bounds p))

Responder

Matriz permutación

Introducción

Ejercicio

Soluciones

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Introducción

Ejercicio

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico