Comprensión

Ancestro común más bajo

PorJosé A. Alonso 1-junio-201811-junio-2018

El tipo de los árboles binarios se define por

   data Arbol = H Int
              | N Int Arbol Arbol

1 2	data Arbol = H Int \| N Int Arbol Arbol

Por ejemplo, el árbol

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

/ \

3 7

/ \ / \

1 4 6 9

se define por

   ejArbol :: Arbol
   ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

1 2	ejArbol :: Arbol ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

   ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

1	ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

   ancestroComunMasBajo ejArbol 4 1  ==  3
   ancestroComunMasBajo ejArbol 1 6  ==  5
   ancestroComunMasBajo ejArbol 6 9  ==  7

ancestroComunMasBajo ejArbol 4 1 == 3

ancestroComunMasBajo ejArbol 1 6 == 5

ancestroComunMasBajo ejArbol 6 9 == 7

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición
-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo1 a x y =
  head [u | u <- xs, u `elem` ys]
  where xs = ancestros a x
        ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol
-- ordenado a, ordenada por profundidad. Por ejemplo,
--    ancestros ejArbol 1 ==  [3,5]
--    ancestros ejArbol 3 ==  [5]
--    ancestros ejArbol 5 ==  []
--    ancestros ejArbol 9 ==  [7,5]
ancestros :: Arbol -> Int -> [Int]
ancestros a y = aux a y []
  where aux (H _)     _ zs = zs
        aux (N x i d) y zs 
          | x == y    = zs
          | y < x     = aux i y (x:zs)
          | otherwise = aux d y (x:zs)

-- 2ª definición
-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo2 (N z i d) x y 
  | x < z && y < z = ancestroComunMasBajo2 i x y 
  | x > z && y > z = ancestroComunMasBajo2 d x y 
  | otherwise      = z

data Arbol = H Int

| N Int Arbol Arbol

ejArbol :: Arbol

ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición

-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo1 a x y =

head [u | u <- xs, u `elem` ys]

where xs = ancestros a x

ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol

-- ordenado a, ordenada por profundidad. Por ejemplo,

-- ancestros ejArbol 1 == [3,5]

-- ancestros ejArbol 3 == [5]

-- ancestros ejArbol 5 == []

-- ancestros ejArbol 9 == [7,5]

ancestros :: Arbol -> Int -> [Int]

ancestros a y = aux a y []

where aux (H _) _ zs = zs

aux (N x i d) y zs

| x == y = zs

| y < x = aux i y (x:zs)

| otherwise = aux d y (x:zs)

-- 2ª definición

-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo2 (N z i d) x y

| x < z && y < z = ancestroComunMasBajo2 i x y

| x > z && y > z = ancestroComunMasBajo2 d x y

| otherwise = z

La regla de los signos de Descartes

PorJosé A. Alonso 30-mayo-20186-junio-2018

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

   cambios :: [Int] -> [(Int,Int)]
   nRaicesPositivas :: [Int] -> [Int]

1 2	cambios :: [Int] -> [(Int,Int)] nRaicesPositivas :: [Int] -> [Int]

tales que

(cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

     cambios [1,3,0,-5,1,-7]  ==  [(3,-5),(-5,1),(1,-7)]

1	cambios [1,3,0,-5,1,-7] == [(3,-5),(-5,1),(1,-7)]

(nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

     nRaicesPositivas [1,3,0,-5,1,-7]  ==  [3,1]

1	nRaicesPositivas [1,3,0,-5,1,-7] == [3,1]

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Soluciones

-- 1ª definición (por comprensión)
-- ===============================

cambios1 :: [Int] -> [(Int,Int)]
cambios1 xs = [(x,y) | (x,y) <- consecutivos (noCeros xs), x*y < 0]
  where consecutivos xs = zip xs (tail xs)

-- (noCeros xs) es la lista de los elementos de xs distintos de cero. 
-- Por ejemplo,  
--    noCeros [1,3,0,-5,1,-7]  ==  [1,3,-5,1,-7]
noCeros :: [Int] -> [Int]
noCeros = filter (/=0)

-- 2ª definición (por recursión)
-- =============================

cambios2 :: [Int] -> [(Int,Int)]
cambios2 xs = cambios2' (noCeros xs)
  where cambios2' (x:y:xs)
          | x*y < 0   = (x,y) : cambios2' (y:xs)
          | otherwise = cambios2' (y:xs)
        cambios2' _ = []

nRaicesPositivas :: [Int] -> [Int]
nRaicesPositivas xs = [n,n-2..0]
  where n = length (cambios1 xs)

-- 1ª definición (por comprensión)

-- ===============================

cambios1 :: [Int] -> [(Int,Int)]

cambios1 xs = [(x,y) | (x,y) <- consecutivos (noCeros xs), x*y < 0]

where consecutivos xs = zip xs (tail xs)

-- (noCeros xs) es la lista de los elementos de xs distintos de cero.

-- Por ejemplo,

-- noCeros [1,3,0,-5,1,-7] == [1,3,-5,1,-7]

noCeros :: [Int] -> [Int]

noCeros = filter (/=0)

-- 2ª definición (por recursión)

-- =============================

cambios2 :: [Int] -> [(Int,Int)]

cambios2 xs = cambios2' (noCeros xs)

where cambios2' (x:y:xs)

| x*y < 0 = (x,y) : cambios2' (y:xs)

| otherwise = cambios2' (y:xs)

cambios2' _ = []

nRaicesPositivas :: [Int] -> [Int]

nRaicesPositivas xs = [n,n-2..0]

where n = length (cambios1 xs)

Números taxicab

PorJosé A. Alonso 29-mayo-20185-junio-2018

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

   taxicab  :: [Integer]
   taxicab2 :: [Integer]

1 2	taxicab :: [Integer] taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

   take 5 taxicab   ==  [1729,4104,13832,20683,32832]
   take 2 taxicab2  ==  [2,1729]

1 2	take 5 taxicab == [1729,4104,13832,20683,32832] take 2 taxicab2 == [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.List  (find)
import Data.Maybe (fromJust)

taxicab :: [Integer]
taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.
-- Por ejemplo,
--    descomposiciones 1729  ==  [(10,9),(12,1)]
--    descomposiciones 1728  ==  [(12,0)]
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(x,y) | x <- [1..round (fromIntegral n ** (1/3))],
           let z = n - x^3,
           let z' = round (fromIntegral z ** (1/3)),
           z'^3 == z,
           let y = z',
           y <= x]

-- 2ª definición de descomposiciones
descomposiciones2 :: Integer -> [(Integer,Integer)]
descomposiciones2 n =
  [(x,y) | x <- [1..raizEnt n 3],
           let z = n - x^3,
           let y = raizEnt z 3,
           y <= x,    
           y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor
-- número entero y tal que y^n <= x. Por ejemplo, 
--    raizEnt  8 3      ==  2
--    raizEnt  9 3      ==  2
--    raizEnt 26 3      ==  2
--    raizEnt 27 3      ==  3
--    raizEnt (10^50) 2 ==  10000000000000000000000000
-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = aux (1,x)
  where aux (a,b) | d == x    = c
                  | c == a    = c
                  | d < x     = aux (c,b)
                  | otherwise = aux (a,c) 
          where c = (a+b) `div` 2
                d = c^n

taxicab2 :: [Integer]
taxicab2 = aux 1 [2..]
  where aux n xs = fx : aux (n+1) [fx+1..]
          where fx = fromJust (find ((== n) . length . descomposiciones) xs)

import Data.List (find)

import Data.Maybe (fromJust)

taxicab :: [Integer]

taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.

-- Por ejemplo,

-- descomposiciones 1729 == [(10,9),(12,1)]

-- descomposiciones 1728 == [(12,0)]

descomposiciones :: Integer -> [(Integer,Integer)]

descomposiciones n =

[(x,y) | x <- [1..round (fromIntegral n ** (1/3))],

let z = n - x^3,

let z' = round (fromIntegral z ** (1/3)),

z'^3 == z,

let y = z',

y <= x]

-- 2ª definición de descomposiciones

descomposiciones2 :: Integer -> [(Integer,Integer)]

descomposiciones2 n =

[(x,y) | x <- [1..raizEnt n 3],

let z = n - x^3,

let y = raizEnt z 3,

y <= x,

y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor

-- número entero y tal que y^n <= x. Por ejemplo,

-- raizEnt 8 3 == 2

-- raizEnt 9 3 == 2

-- raizEnt 26 3 == 2

-- raizEnt 27 3 == 3

-- raizEnt (10^50) 2 == 10000000000000000000000000

-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^n

taxicab2 :: [Integer]

taxicab2 = aux 1 [2..]

where aux n xs = fx : aux (n+1) [fx+1..]

where fx = fromJust (find ((== n) . length . descomposiciones) xs)

Problema de las 3 jarras

PorJosé A. Alonso 23-mayo-201830-mayo-2018

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

   solucionesTresJarras :: Problema -> [[Estado]]
   tresJarras :: Problema -> Maybe [Estado]

1 2	solucionesTresJarras :: Problema -> [[Estado]] tresJarras :: Problema -> Maybe [Estado]

tales que

(solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

     λ> mapM_ print (solucionesTresJarras (4,2,1))
     [(4,0,0),(2,2,0)]
     [(4,0,0),(3,0,1),(1,2,1),(2,2,0)]
     [(4,0,0),(3,0,1),(3,1,0),(2,2,0)]
     [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]
     [(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]
     λ> mapM_ print (solucionesTresJarras (8,6,2))
     [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
     [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
     [(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
     [(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]
     [(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
     [(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
     [(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
     [(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
     λ> length (solucionesTresJarras (8,5,3))
     16
     λ> head (solucionesTresJarras (8,5,3))
     [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
     λ> length (solucionesTresJarras (8,6,5))
     0

λ> mapM_ print (solucionesTresJarras (4,2,1))

[(4,0,0),(2,2,0)]

[(4,0,0),(3,0,1),(1,2,1),(2,2,0)]

[(4,0,0),(3,0,1),(3,1,0),(2,2,0)]

[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]

[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]

λ> mapM_ print (solucionesTresJarras (8,6,2))

[(8,0,0),(2,6,0),(2,4,2),(4,4,0)]

[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]

[(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]

[(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]

[(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]

[(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]

[(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]

[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]

λ> length (solucionesTresJarras (8,5,3))

λ> head (solucionesTresJarras (8,5,3))

[(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]

λ> length (solucionesTresJarras (8,6,5))

(tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

     λ> tresJarras (4,2,1)
     Just [(4,0,0),(2,2,0)]
     λ> tresJarras (8,6,2)
     Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
     λ> tresJarras (8,5,3)
     Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
     λ> tresJarras (8,6,5)
     Nothing

λ> tresJarras (4,2,1)

Just [(4,0,0),(2,2,0)]

λ> tresJarras (8,6,2)

Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]

λ> tresJarras (8,5,3)

Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]

λ> tresJarras (8,6,5)

Nothing

Soluciones

import Data.Maybe (listToMaybe)

-- Para simplificar la notación se definen los tipos Problema y Estado
-- como sigue.

-- Un problema es una terna de números. El primero es la capacidad de la
-- primera jarra, el segundo el de la segunda y el tercero el de la
-- tercera.
type Problema = (Int,Int,Int)

-- Un estado es una terna de números. El primero es el contenido de la
-- jarra de A litros, el segundo el de la de B litros y el tercero el de
-- la de C litros.
type Estado = (Int,Int,Int)

solucionesTresJarras :: Problema -> [[Estado]]
solucionesTresJarras p = busca [[inicial p]]
  where
    busca []        = []
    busca ((e:es):ns)  
      | esFinal p e = reverse (e:es) : busca ns
      | otherwise   = busca (ns ++ [e1:e:es | e1 <- sucesores p e
                                            , e1 `notElem` es])

-- (inicial p) es el estado inicial del problema p. Por ejemplo, 
--    inicial (8,5,3)  ==  (8,0,0)
inicial :: Problema -> Estado
inicial (a,_,_) = (a,0,0)

-- (esFinal p e) es verifica si e es un estado final del problema de las
-- tres jarras p. Por ejemplo,
--    esFinal (8,5,3) (4,4,0)  ==  True
--    esFinal (8,5,3) (4,0,4)  ==  False
esFinal :: Problema -> Estado -> Bool
esFinal (a,_,_) (x,y,z) =
  x == y && x + y == a

-- (sucesores p e) es la lista de los sucesores del estado e en el
-- problema de las tres jarras p. Por ejemplo, 
--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]
--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]
sucesores :: Problema -> Estado -> [Estado]
sucesores (a,b,c) (x,y,z) =
     [(x-ab,y+ab,z)    | let ab = min x (b-y), ab > 0]
  ++ [(x-ac,y   ,z+ac) | let ac = min x (c-z), ac > 0]
  ++ [(x+ba,y-ba,z)    | let ba = min y (a-x), ba > 0]
  ++ [(x   ,y-bc,z+bc) | let bc = min y (c-z), bc > 0]
  ++ [(x+ca,y   ,z-ca) | let ca = min z (a-x), ca > 0]
  ++ [(x   ,y+cb,z-cb) | let cb = min z (b-y), cb > 0]
  
tresJarras :: Problema -> Maybe [Estado]
tresJarras p = listToMaybe (solucionesTresJarras p)

import Data.Maybe (listToMaybe)

-- Para simplificar la notación se definen los tipos Problema y Estado

-- como sigue.

-- Un problema es una terna de números. El primero es la capacidad de la

-- primera jarra, el segundo el de la segunda y el tercero el de la

-- tercera.

type Problema = (Int,Int,Int)

-- Un estado es una terna de números. El primero es el contenido de la

-- jarra de A litros, el segundo el de la de B litros y el tercero el de

-- la de C litros.

type Estado = (Int,Int,Int)

solucionesTresJarras :: Problema -> [[Estado]]

solucionesTresJarras p = busca [[inicial p]]

where

busca [] = []

busca ((e:es):ns)

| esFinal p e = reverse (e:es) : busca ns

| otherwise = busca (ns ++ [e1:e:es | e1 <- sucesores p e

, e1 `notElem` es])

-- (inicial p) es el estado inicial del problema p. Por ejemplo,

-- inicial (8,5,3) == (8,0,0)

inicial :: Problema -> Estado

inicial (a,_,_) = (a,0,0)

-- (esFinal p e) es verifica si e es un estado final del problema de las

-- tres jarras p. Por ejemplo,

-- esFinal (8,5,3) (4,4,0) == True

-- esFinal (8,5,3) (4,0,4) == False

esFinal :: Problema -> Estado -> Bool

esFinal (a,_,_) (x,y,z) =

x == y && x + y == a

-- (sucesores p e) es la lista de los sucesores del estado e en el

-- problema de las tres jarras p. Por ejemplo,

-- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)]

-- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)]

sucesores :: Problema -> Estado -> [Estado]

sucesores (a,b,c) (x,y,z) =

[(x-ab,y+ab,z) | let ab = min x (b-y), ab > 0]

++ [(x-ac,y ,z+ac) | let ac = min x (c-z), ac > 0]

++ [(x+ba,y-ba,z) | let ba = min y (a-x), ba > 0]

++ [(x ,y-bc,z+bc) | let bc = min y (c-z), bc > 0]

++ [(x+ca,y ,z-ca) | let ca = min z (a-x), ca > 0]

++ [(x ,y+cb,z-cb) | let cb = min z (b-y), cb > 0]

tresJarras :: Problema -> Maybe [Estado]

tresJarras p = listToMaybe (solucionesTresJarras p)

Representaciones de grafos

PorJosé A. Alonso 22-mayo-201829-mayo-2018

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

   1 ----- 2
   | \     |
   |  3    |
   | /     |
   4 ----- 5

1 ----- 2

| \ |

| 3 |

| / |

4 ----- 5

se puede representar por la matriz de adyacencia

   |0 1 1 1 0|
   |1 0 0 0 1|
   |1 0 0 1 0|
   |1 0 1 0 1|
   |0 1 0 1 0|

|0 1 1 1 0|

|1 0 0 0 1|

|1 0 0 1 0|

|1 0 1 0 1|

|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

   [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

1	[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

   matrizAlista :: Matrix Int -> [(Int,[Int])]
   listaAmatriz :: [(Int,[Int])] -> Matrix Int

1 2	matrizAlista :: Matrix Int -> [(Int,[Int])] listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

(matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por

     ejMatriz :: Matrix Int
     ejMatriz = fromLists [[0,1,1,1,0],
                           [1,0,0,0,1],
                           [1,0,0,1,0],
                           [1,0,1,0,1],
                           [0,1,0,1,0]]

ejMatriz :: Matrix Int

ejMatriz = fromLists [[0,1,1,1,0],

[1,0,0,0,1],

[1,0,0,1,0],

[1,0,1,0,1],

[0,1,0,1,0]]

se tiene que

     λ> matrizAlista ejMatriz
     [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

1 2	λ> matrizAlista ejMatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

(listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,

     λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
     ( 0 1 1 1 0 )
     ( 1 0 0 0 1 )
     ( 1 0 0 1 0 )
     ( 1 0 1 0 1 )
     ( 0 1 0 1 0 )
     λ> matrizAlista it
     [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

( 0 1 1 1 0 )

( 1 0 0 0 1 )

( 1 0 0 1 0 )

( 1 0 1 0 1 )

( 0 1 0 1 0 )

λ> matrizAlista it

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Soluciones

import Data.List (sort)
import Data.Matrix

ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
                      [1,0,0,0,1],
                      [1,0,0,1,0],
                      [1,0,1,0,1],
                      [0,1,0,1,0]]

matrizAlista :: Matrix Int -> [(Int,[Int])]
matrizAlista a = 
  [(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]]
  where n = nrows a

listaAmatriz :: [(Int,[Int])] -> Matrix Int
listaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps]
  where n = length ps
        fila n xs = [f i | i <- [1..n]]
          where f i | i `elem` xs = 1
                    | otherwise   = 0

import Data.List (sort)

import Data.Matrix

ejMatriz :: Matrix Int

ejMatriz = fromLists [[0,1,1,1,0],

[1,0,0,0,1],

[1,0,0,1,0],

[1,0,1,0,1],

[0,1,0,1,0]]

matrizAlista :: Matrix Int -> [(Int,[Int])]

matrizAlista a =

[(i,[j | j <- [1..n], a!(i,j) == 1]) | i <- [1..n]]

where n = nrows a

listaAmatriz :: [(Int,[Int])] -> Matrix Int

listaAmatriz ps = fromLists [fila n xs | (_,xs) <- sort ps]

where n = length ps

fila n xs = [f i | i <- [1..n]]

where f i | i `elem` xs = 1

| otherwise = 0

Ancestro común más bajo

Soluciones

La regla de los signos de Descartes

Soluciones

Números taxicab

Soluciones

Problema de las 3 jarras

Soluciones

Representaciones de grafos

Soluciones

Entradas recientes

Buscar

Correo electrónico