Exercitium

Algoritmo de bajada para resolver un sistema triangular inferior

PorJosé A. Alonso 15-junio-201528-octubre-2015

Un sistema de ecuaciones lineales Ax = b es triangular inferior si todos los elementos de la matriz A que están por encima de la diagonal principal son nulos; es decir, es de la forma

   a(1,1)*x(1)                                               = b(1)
   a(2,1)*x(1) + a(2,2)*x(2)                                 = b(2)
   a(3,1)*x(1) + a(3,2)*x(2) + a(3,3)*x(3)                   = b(3)
   ...
   a(n,1)*x(1) + a(n,2)*x(2) + a(n,3)*x(3) +...+ a(x,x)*x(n) = b(n)

a(1,1)*x(1) = b(1)

a(2,1)*x(1) + a(2,2)*x(2) = b(2)

a(3,1)*x(1) + a(3,2)*x(2) + a(3,3)*x(3) = b(3)

...

a(n,1)*x(1) + a(n,2)*x(2) + a(n,3)*x(3) +...+ a(x,x)*x(n) = b(n)

El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada:

   x(1) = b(1) / a(1,1)
   x(2) = (b(2) - a(2,1)*x(1)) / a(2,2)
   x(3) = (b(3) - a(3,1)*x(1) - a(3,2)*x(2)) / a(3,3)
   ...
   x(n) = (b(n) - a(n,1)*x(1) - a(n,2)*x(2) -...- a(n,n-1)*x(n-1)) / a(n,n)

x(1) = b(1) / a(1,1)

x(2) = (b(2) - a(2,1)*x(1)) / a(2,2)

x(3) = (b(3) - a(3,1)*x(1) - a(3,2)*x(2)) / a(3,3)

...

x(n) = (b(n) - a(n,1)*x(1) - a(n,2)*x(2) -...- a(n,n-1)*x(n-1)) / a(n,n)

Definir la función

   bajada :: Matrix Double -> Matrix Double -> Matrix Double

1	bajada :: Matrix Double -> Matrix Double -> Matrix Double

tal que (bajada a b) es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,

   ghci> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]]
   ghci> let b = fromLists [[3],[6.5],[10]]
   ghci> bajada a b
   ( 1.5 )
   ( 2.0 )
   ( 0.0 )

ghci> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]]

ghci> let b = fromLists [[3],[6.5],[10]]

ghci> bajada a b

( 1.5 )

( 2.0 )

( 0.0 )

Es decir, la solución del sistema

   2x            = 3
   3x + y        = 6.5
   4x + 2y + 5 z = 10

2x = 3

3x + y = 6.5

4x + 2y + 5 z = 10

es x=1.5, y=2 y z=0.

Soluciones

import Data.Matrix

bajada :: Matrix Double -> Matrix Double -> Matrix Double
bajada a b = fromLists [[x i] | i <- [1..m]]
    where m = nrows a
          x k = (b!(k,1) - sum [a!(k,j) * x j | j <- [1..k-1]]) / a!(k,k)

import Data.Matrix

bajada :: Matrix Double -> Matrix Double -> Matrix Double

bajada a b = fromLists [[x i] | i <- [1..m]]

where m = nrows a

x k = (b!(k,1) - sum [a!(k,j) * x j | j <- [1..k-1]]) / a!(k,k)

Mayor producto de n números adyacentes en una matriz

PorJosé A. Alonso 12-junio-201528-octubre-2015

Definir la función

   mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]

1	mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]

tal que (mayorProductoAdyacentes n p) es la lista de los segmentos formados por n elementos adyacentes en la misma fila, columna o diagonal de la matriz p cuyo productos son máximo. Por ejemplo,

   ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12])
   [[10,11,12]]
   ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
   [[3,7,9]]
   ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2])
   [[3,4],[4,3]]
   ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3])
   [[2,3],[2,3]]
   ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3])
   [[3,4],[4,3]]
   ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3])
   [[5,4]]
   ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
   [[3,7,9]]

ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12])

[[10,11,12]]

ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])

[[3,7,9]]

ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2])

[[3,4],[4,3]]

ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3])

[[2,3],[2,3]]

ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3])

[[3,4],[4,3]]

ghci> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3])

[[5,4]]

ghci> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])

[[3,7,9]]

Soluciones

import Data.Array

type Matriz a = Array (Int,Int) a

mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]
mayorProductoAdyacentes n p = 
    [xs | xs <- segmentos, product xs == m]
    where segmentos = adyacentes n p 
          m         = maximum (map product segmentos)

-- (adyacentes n p) es la lista de los segmentos de longitud n de las
-- líneas de la matriz p. Por ejemplo,
--    ghci> adyacentes 3 (listArray ((1,1),(3,4)) [1..12])
--    [[1,2,3],[2,3,4],[5,6,7],[6,7,8],[9,10,11],[10,11,12],[1,5,9],
--     [2,6,10],[3,7,11],[4,8,12],[1,6,11],[2,7,12],[3,6,9],[4,7,10]]
adyacentes :: Num a => Int -> Matriz a -> [[a]]
adyacentes n p = concatMap (segmentos n) (lineas p)

-- (lineas p) es la lista de las líneas de la matriz p. Por ejemplo, 
--    ghci> lineas (listArray ((1,1),(3,4)) [1..12])
--    [[1,2,3,4],[5,6,7,8],[9,10,11,12],
--     [1,5,9],[2,6,10],[3,7,11],[4,8,12],
--     [9],[5,10],[1,6,11],[2,7,12],[3,8],[4],
--     [1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]
lineas :: Num a => Matriz a -> [[a]]
lineas p = filas p ++ 
           columnas p ++ 
           diagonalesPrincipales p ++
           diagonalesSecundarias p

-- (filas p) es la lista de las filas de la matriz p. Por ejemplo,
--    ghci> filas (listArray ((1,1),(3,4)) [1..12])
--    [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
filas :: Num a => Matriz a -> [[a]]
filas p = [fila i p | i <- [1..m]]
    where (_,(m,_)) = bounds p

-- (fila i p) es la fila i-ésima de la matriz p. Por ejemplo, 
--    fila 2 (listArray ((1,1),(3,4)) [1..12])  ==  [5,6,7,8]
fila :: Num a => Int -> Matriz a -> [a]
fila i p = [p!(i,j) | j <- [1..n]]
    where (_,(_,n)) = bounds p

-- (columnas p) es la lista de las columnas de la matriz p. Por ejemplo,
--    ghci> columnas (listArray ((1,1),(3,4)) [1..12])
--    [[1,5,9],[2,6,10],[3,7,11],[4,8,12]]
columnas :: Num a => Matriz a -> [[a]]
columnas p = [columna j p | j <- [1..n]]
    where (_,(_,n)) = bounds p

-- (columna j p) es la columna j-ésima de la matriz p. Por ejemplo, 
--    columna 2 (listArray ((1,1),(3,4)) [1..12])  ==  [2,6,10]
columna :: Num a => Int -> Matriz a -> [a]
columna j p = [p!(i,j) | i <- [1..m]]
    where (_,(m,_)) = bounds p

-- (diagonalesPrincipales p) es la lista de las diagonales principales
-- de p. Por ejemplo, 
--    ghci> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])
--    [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
diagonalesPrincipales :: Matriz a -> [[a]]
diagonalesPrincipales p = 
    [[p!ij1 | ij1 <- extension ij] | ij <- iniciales] 
    where (_,(m,n)) = bounds p
          iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]] 
          extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]

-- (diagonalesSecundarias p) es la lista de las diagonales secundarias
-- de p. Por ejemplo, 
--    ghci> diagonalesSecundarias (listArray ((1,1),(3,4)) [1..12])
--    [[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]
diagonalesSecundarias p = 
    [[p!ij1 | ij1 <- extension ij] | ij <- iniciales]
    where (_,(m,n)) = bounds p
          iniciales = [(1,j) | j <- [1..n]] ++ [(i,n) | i <- [2..m]] 
          extension (i,j) = [(i+k,j-k) | k <- [0..min (j-1) (m-i)]]

-- (segmentos n xs) es la lista de los segmentos de longitud n de la
-- lista xs. Por ejemplo, 
--    segmentos 3 [1..5]  ==  [[1,2,3],[2,3,4],[3,4,5]]
segmentos :: Int -> [a] -> [[a]]
segmentos n xs 
    | length xs < n = []
    | otherwise     = take n xs : segmentos n (tail xs)

import Data.Array

type Matriz a = Array (Int,Int) a

mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]

mayorProductoAdyacentes n p =

[xs | xs <- segmentos, product xs == m]

where segmentos = adyacentes n p

m = maximum (map product segmentos)

-- (adyacentes n p) es la lista de los segmentos de longitud n de las

-- líneas de la matriz p. Por ejemplo,

-- ghci> adyacentes 3 (listArray ((1,1),(3,4)) [1..12])

-- [[1,2,3],[2,3,4],[5,6,7],[6,7,8],[9,10,11],[10,11,12],[1,5,9],

-- [2,6,10],[3,7,11],[4,8,12],[1,6,11],[2,7,12],[3,6,9],[4,7,10]]

adyacentes :: Num a => Int -> Matriz a -> [[a]]

adyacentes n p = concatMap (segmentos n) (lineas p)

-- (lineas p) es la lista de las líneas de la matriz p. Por ejemplo,

-- ghci> lineas (listArray ((1,1),(3,4)) [1..12])

-- [[1,2,3,4],[5,6,7,8],[9,10,11,12],

-- [1,5,9],[2,6,10],[3,7,11],[4,8,12],

-- [9],[5,10],[1,6,11],[2,7,12],[3,8],[4],

-- [1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]

lineas :: Num a => Matriz a -> [[a]]

lineas p = filas p ++

columnas p ++

diagonalesPrincipales p ++

diagonalesSecundarias p

-- (filas p) es la lista de las filas de la matriz p. Por ejemplo,

-- ghci> filas (listArray ((1,1),(3,4)) [1..12])

-- [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

filas :: Num a => Matriz a -> [[a]]

filas p = [fila i p | i <- [1..m]]

where (_,(m,_)) = bounds p

-- (fila i p) es la fila i-ésima de la matriz p. Por ejemplo,

-- fila 2 (listArray ((1,1),(3,4)) [1..12]) == [5,6,7,8]

fila :: Num a => Int -> Matriz a -> [a]

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

where (_,(_,n)) = bounds p

-- (columnas p) es la lista de las columnas de la matriz p. Por ejemplo,

-- ghci> columnas (listArray ((1,1),(3,4)) [1..12])

-- [[1,5,9],[2,6,10],[3,7,11],[4,8,12]]

columnas :: Num a => Matriz a -> [[a]]

columnas p = [columna j p | j <- [1..n]]

where (_,(_,n)) = bounds p

-- (columna j p) es la columna j-ésima de la matriz p. Por ejemplo,

-- columna 2 (listArray ((1,1),(3,4)) [1..12]) == [2,6,10]

columna :: Num a => Int -> Matriz a -> [a]

columna j p = [p!(i,j) | i <- [1..m]]

where (_,(m,_)) = bounds p

-- (diagonalesPrincipales p) es la lista de las diagonales principales

-- de p. Por ejemplo,

-- ghci> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12])

-- [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]

diagonalesPrincipales :: Matriz a -> [[a]]

diagonalesPrincipales p =

[[p!ij1 | ij1 <- extension ij] | ij <- iniciales]

where (_,(m,n)) = bounds p

iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]]

extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]]

-- (diagonalesSecundarias p) es la lista de las diagonales secundarias

-- de p. Por ejemplo,

-- ghci> diagonalesSecundarias (listArray ((1,1),(3,4)) [1..12])

-- [[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]

diagonalesSecundarias p =

[[p!ij1 | ij1 <- extension ij] | ij <- iniciales]

where (_,(m,n)) = bounds p

iniciales = [(1,j) | j <- [1..n]] ++ [(i,n) | i <- [2..m]]

extension (i,j) = [(i+k,j-k) | k <- [0..min (j-1) (m-i)]]

-- (segmentos n xs) es la lista de los segmentos de longitud n de la

-- lista xs. Por ejemplo,

-- segmentos 3 [1..5] == [[1,2,3],[2,3,4],[3,4,5]]

segmentos :: Int -> [a] -> [[a]]

segmentos n xs

| length xs < n = []

| otherwise = take n xs : segmentos n (tail xs)

Método de bisección para encontrar raíces de funciones

PorJosé A. Alonso 11-junio-201528-octubre-2015

El método de bisección para calcular un cero de una función en el intervalo
[a,b] se basa en el teorema de Bolzano:

Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0″.

El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:

Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
Si no, repetir el proceso en el intervalo [c,b].

Definir la función

   biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

1	biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,

   biseccion (\x -> x^2 - 3) 0 5 0.01             ==  1.7333984375
   biseccion (\x -> x^3 - x - 2) 0 4 0.01         ==  1.521484375
   biseccion cos 0 2 0.01                         ==  1.5625
   biseccion (\x -> log (50-x) - 4) (-10) 3 0.01  ==  -5.125

biseccion (\x -> x^2 - 3) 0 5 0.01 == 1.7333984375

biseccion (\x -> x^3 - x - 2) 0 4 0.01 == 1.521484375

biseccion cos 0 2 0.01 == 1.5625

biseccion (\x -> log (50-x) - 4) (-10) 3 0.01 == -5.125

Soluciones

-- 1ª solución
biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double
biseccion f a b e  
    | abs (f c) < e   = c
    | (f a)*(f c) < 0 = biseccion f a c e
    | otherwise       = biseccion f c b e
    where c = (a+b)/2

-- 2ª solución
biseccion2 :: (Double -> Double) -> Double -> Double -> Double -> Double
biseccion2 f a b e = aux a b
    where aux a b | abs (f c) < e   = c
                  | (f a)*(f c) < 0 = aux a c 
                  | otherwise       = aux c b
                  where c = (a+b)/2

-- 1ª solución

biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

biseccion f a b e

| abs (f c) < e = c

| (f a)*(f c) < 0 = biseccion f a c e

| otherwise = biseccion f c b e

where c = (a+b)/2

-- 2ª solución

biseccion2 :: (Double -> Double) -> Double -> Double -> Double -> Double

biseccion2 f a b e = aux a b

where aux a b | abs (f c) < e = c

| (f a)*(f c) < 0 = aux a c

| otherwise = aux c b

where c = (a+b)/2

Descomposiciones en sumas de primos

PorJosé A. Alonso 4-junio-201513-junio-2015

Definir la función

   sumaDePrimos :: Int -> [[Int]]

1	sumaDePrimos :: Int -> [[Int]]

tal que (sumaDePrimos x) es la lista de las listas no crecientes de números primos que suman x. Por ejemplo,

   sumaDePrimos 10  ==  [[7,3],[5,5],[5,3,2],[3,3,2,2],[2,2,2,2,2]]
   sumaDePrimos 0   ==  []
   sumaDePrimos 1   ==  []

sumaDePrimos 10 == [[7,3],[5,5],[5,3,2],[3,3,2,2],[2,2,2,2,2]]

sumaDePrimos 0 == []

sumaDePrimos 1 == []

Soluciones

import Data.Numbers.Primes (primes)

sumaDePrimos :: Integer -> [[Integer]]
sumaDePrimos n = aux n (reverse (takeWhile (<=n) primes))
    where aux _ [] = []
          aux n (x:xs) | x > n     = aux n xs
                       | x == n    = [n] : aux n xs
                       | otherwise = map (x:) (aux (n-x) (x:xs)) ++ aux n xs

import Data.Numbers.Primes (primes)

sumaDePrimos :: Integer -> [[Integer]]

sumaDePrimos n = aux n (reverse (takeWhile (<=n) primes))

where aux _ [] = []

aux n (x:xs) | x > n = aux n xs

| x == n = [n] : aux n xs

| otherwise = map (x:) (aux (n-x) (x:xs)) ++ aux n xs

Caminos en un grafo

PorJosé A. Alonso 2-junio-201526-marzo-2022

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

1 2	grafo :: [(Int,Int)] -> Grafo Int Int caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

(grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,

     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

1 2	ghci> grafo [(2,4),(4,5)] G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])

(caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,

     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
     [[1,3,5,7],[1,3,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
     [[2,5,3,7],[2,5,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
     [[1,3,5,2],[1,3,7,5,2]]
     ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
     []
     ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
     109601

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)

[[1,3,5,7],[1,3,7]]

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)

[[2,5,3,7],[2,5,7]]

ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)

[[1,3,5,2],[1,3,7,5,2]]

ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4

[]

ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Soluciones

import Data.List (sort)
import I1M.Grafo
import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int
grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]
    where ns = map fst as ++ map snd as
          m  = minimum ns
          n  = maximum ns

-- 1ª solución
-- ===========

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux [[b]] where 
    aux [] = []
    aux ((x:xs):yss)
        | x == a    = (x:xs) : aux yss
        | otherwise = aux ([z:x:xs | z <- adyacentes g x
                                   , z `notElem` (x:xs)] 
                           ++ yss) 

-- 2ª solución (mediante espacio de estados)
-- =========================================

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos2 g a b = buscaEE sucesores esFinal inicial
    where inicial          = [b]
          sucesores (x:xs) = [z:x:xs | z <- adyacentes g x
                                     , z `notElem` (x:xs)] 
          esFinal (x:xs)   = x == a

-- Comparación de eficiencia
-- =========================

--    ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.57 secs, 500533816 bytes)
--    ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.53 secs, 470814096 bytes)

import Data.List (sort)

import I1M.Grafo

import I1M.BusquedaEnEspaciosDeEstados

grafo :: [(Int,Int)] -> Grafo Int Int

grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]

where ns = map fst as ++ map snd as

m = minimum ns

n = maximum ns

-- 1ª solución

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

caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos g a b = aux [[b]] where

aux [] = []

aux ((x:xs):yss)

| x == a = (x:xs) : aux yss

| otherwise = aux ([z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

++ yss)

-- 2ª solución (mediante espacio de estados)

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

caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]

caminos2 g a b = buscaEE sucesores esFinal inicial

where inicial = [b]

sucesores (x:xs) = [z:x:xs | z <- adyacentes g x

, z `notElem` (x:xs)]

esFinal (x:xs) = x == a

-- Comparación de eficiencia

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

-- ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.57 secs, 500533816 bytes)

-- ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)

-- 109601

-- (3.53 secs, 470814096 bytes)

Algoritmo de bajada para resolver un sistema triangular inferior

Soluciones

Mayor producto de n números adyacentes en una matriz

Soluciones

Método de bisección para encontrar raíces de funciones

Soluciones

Descomposiciones en sumas de primos

Soluciones

Caminos en un grafo

Soluciones

Entradas recientes

Buscar

Correo electrónico