Caminos minimales en un árbol numérico

PorJosé A. Alonso 7-diciembre-201725-abril-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

1	ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

λ> putStrLn (drawTree (fmap show ej))

+- 5

| |

| `- 9

`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

/ \

5 3

| |

4 2

/ \ |

3 2 1

| |

2 1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

mayoresDivisores :: Int -> [Int]

arbol :: Int -> Tree Int

caminos :: Int -> [[Int]]

caminosMinimales :: Int -> [[Int]]

tales que

(mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []

mayoresDivisores 24 == [12,8,6]

mayoresDivisores 16 == [8,4]

mayoresDivisores 10 == [5]

mayoresDivisores 17 == []

(arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1

λ> putStrLn (drawTree (fmap show (arbol 6)))

+- 5

| |

| `- 4

| |

| +- 3

| | |

| | `- 2

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 3

`- 2

`- 1

(caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

1 2	λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

(caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

λ> caminosMinimales 6

[[6,3,2,1]]

λ> caminosMinimales 17

[[17,16,4,2,1]]

λ> caminosMinimales 50

[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree

mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  

arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol

--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

import Data.Tree

mayoresDivisores :: Int -> [Int]

mayoresDivisores x =

[max u v | u <- [2..floor (sqrt (fromIntegral x))]

, x `mod` u == 0

, let v = x `div` u]

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])

caminos :: Int -> [[Int]]

caminos = caminosArbol . arbol

-- λ> caminosArbol (arbol 6)

-- [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

caminosArbol :: Tree a -> [[a]]

caminosArbol (Node x []) = [[x]]

caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]

caminosBosque :: Forest a -> [[a]]

caminosBosque = concatMap caminosArbol

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [ys | ys <- yss, length ys == m]

where yss = caminos x

m = minimum (map length yss)

6 Comentarios

import Data.Numbers.Primes (primeFactors)
import Data.List (sort,group,inits)
import Data.Tree (Tree (Node),drawTree)

mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  takeWhile (>= (ceiling . sqrt . fromIntegral $ x))
  . tail . reverse . divisores $ x

divisores :: Int -> [Int]
divisores =
  sort
  . map (product . concat)
  . producto
  . map (inits)
  . group
  . primeFactors
 
producto :: [[a]] -> [[a]]
producto = foldr f [[]]
   where f :: [a] -> [[a]] -> [[a]]
         f xs xss = [x:ys | x <- xs, ys <- xss]

arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x $ map arbol (pred x : mayoresDivisores x)

caminos :: Int -> [[Int]]
caminos = ramas . arbol

ramas :: Tree Int -> [[Int]]
ramas (Node a [])     = [[a]]
ramas (Node a bosque) = map (a:) $ concat $ map ramas bosque

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = filter (long m) . caminos $ x
  where m = minimum . map (length) . caminos $ x

long :: Int -> [Int] -> Bool
long m xs = length xs == m

import Data.Numbers.Primes (primeFactors)

import Data.List (sort,group,inits)

import Data.Tree (Tree (Node),drawTree)

mayoresDivisores :: Int -> [Int]

mayoresDivisores x =

takeWhile (>= (ceiling . sqrt . fromIntegral $ x))

. tail . reverse . divisores $ x

divisores :: Int -> [Int]

divisores =

sort

. map (product . concat)

. producto

. map (inits)

. group

. primeFactors

producto :: [[a]] -> [[a]]

producto = foldr f [[]]

where f :: [a] -> [[a]] -> [[a]]

f xs xss = [x:ys | x <- xs, ys <- xss]

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x $ map arbol (pred x : mayoresDivisores x)

caminos :: Int -> [[Int]]

caminos = ramas . arbol

ramas :: Tree Int -> [[Int]]

ramas (Node a []) = [[a]]

ramas (Node a bosque) = map (a:) $ concat $ map ramas bosque

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = filter (long m) . caminos $ x

where m = minimum . map (length) . caminos $ x

long :: Int -> [Int] -> Bool

long m xs = length xs == m

Responder

En la definición de ramas se puede sustituir la expresión «concat $ map ramas bosque» por «concatMap ramas bosque»:

caminos :: Int -> [[Int]]
caminos = ramas . arbol

ramas :: Tree Int -> [[Int]]
ramas (Node a [])    = [[a]]
ramas (Node a bosque) = map (a:) $ concatMap ramas bosque

caminos :: Int -> [[Int]]

caminos = ramas . arbol

ramas :: Tree Int -> [[Int]]

ramas (Node a []) = [[a]]

ramas (Node a bosque) = map (a:) $ concatMap ramas bosque

Responder

import Data.Tree
import Data.List

mayoresDivisores :: Int -> [Int]
mayoresDivisores x = [ y | y <- [x-1,x-2..z], x `mod` y == 0]
  where z = (ceiling . sqrt . fromIntegral) x
 
arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x ([arbol (x-1)] ++ mD)
  where mD = map arbol (mayoresDivisores x)  
 
caminos :: Int -> [[Int]]
caminos x = aux (arbol x)
  where aux (Node 1 [])  = [[1]]
        aux (Node e trs) = (map (e:) (concat (map aux trs))) 
 
caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [xs | xs <- cam, length xs == y]
  where cam = caminos x
        y   = (length . minimum) cam

import Data.Tree

import Data.List

mayoresDivisores :: Int -> [Int]

mayoresDivisores x = [ y | y <- [x-1,x-2..z], x `mod` y == 0]

where z = (ceiling . sqrt . fromIntegral) x

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol x = Node x ([arbol (x-1)] ++ mD)

where mD = map arbol (mayoresDivisores x)

caminos :: Int -> [[Int]]

caminos x = aux (arbol x)

where aux (Node 1 []) = [[1]]

aux (Node e trs) = (map (e:) (concat (map aux trs)))

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [xs | xs <- cam, length xs == y]

where cam = caminos x

y = (length . minimum) cam

Responder

Buenas, la definición de caminosMinimales no es correcta. Por ejemplo:

-- λ> caminosMinimales 33
-- [[33,32,16,4,2,1],[33,32,8,4,2,1]]
-- λ> caminosMinimales2 33
-- [[33,32,16,8,4,2,1],[33,32,16,4,3,2,1],[33,32,8,4,3,2,1],[33,11,10,9,3,2,1],[33,11,10,5,4,2,1]]

-- λ> caminosMinimales 33

-- [[33,32,16,4,2,1],[33,32,8,4,2,1]]

-- λ> caminosMinimales2 33

-- [[33,32,16,8,4,2,1],[33,32,16,4,3,2,1],[33,32,8,4,3,2,1],[33,11,10,9,3,2,1],[33,11,10,5,4,2,1]]

Donde caminosMinimales2 es tu función.

Responder

No estaba muy seguro de como la función minimum funcionaba en esos casos, pero parecía funcionar xD.
Creo que esta nueva definición soluciona el problema.

caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ xs | (xs,l) <- zip cam long , l == y]
  where cam = caminos x
        long = map length cam
        y = minimum long

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = [ xs | (xs,l) <- zip cam long , l == y]

where cam = caminos x

long = map length cam

y = minimum long

Responder

Un intento de solución de un iniciado en la programación dinámica en Haskell.
He decido hacer el array de tamaño 300 porque mayor que este tamaño ya tarda demasiado en hacerme el árbol y aunque realmente mi idea inicial era hacerlo de tamaño n no tengo ni idea de como, también podría haber usado vectores pero tampoco sé como funcionan estos en Haskell.
He hecho algo parecido a la función árbol con la función caminos y para la función caminosMinimales simplemente he usado la de angruicam1, aunque se puede optimizar con un método parecido al de la función caminos.

import Data.List
import Data.Array
import Data.Numbers.Primes
import Data.Tree

mayoresDivisores :: Int -> [Int]
mayoresDivisores 1 = []
mayoresDivisores n = (reverse.init.drop (numDivisores `div` 2)) (divisores)
  where numDivisores = product[(length k) + 1 | k<-u]
        divisores    = (sort.posibles) u
          where posibles [xs] = [(head xs)^k  | k<-[0..length xs]]
                posibles (xs:xss) = [(head xs)^k * e | k<-[0..length xs], e<-posibles xss]
        u = (group.primeFactors) n
    
arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol n = Node n (ar!(n-1):[ar!k | k<-mayoresDivisores n]) 

ar = array (1,300) [(i, arbol i) |  i<-[1..300]]

caminos :: Int -> [[Int]]
caminos 1 = [[1]]
caminos n = concat [map (n:) (ca!k) | k<-((n-1):mayoresDivisores n)]

ca = array (1,300) [(i, caminos i) | i<-[1..300]]
                   
caminosMinimales :: Int -> [[Int]]
caminosMinimales x = filter (long m) . caminos $ x
  where m = minimum . map (length) . caminos $ x

long :: Int -> [Int] -> Bool
long m xs = length xs == m

import Data.List

import Data.Array

import Data.Numbers.Primes

import Data.Tree

mayoresDivisores :: Int -> [Int]

mayoresDivisores 1 = []

mayoresDivisores n = (reverse.init.drop (numDivisores `div` 2)) (divisores)

where numDivisores = product[(length k) + 1 | k<-u]

divisores = (sort.posibles) u

where posibles [xs] = [(head xs)^k | k<-[0..length xs]]

posibles (xs:xss) = [(head xs)^k * e | k<-[0..length xs], e<-posibles xss]

u = (group.primeFactors) n

arbol :: Int -> Tree Int

arbol 1 = Node 1 []

arbol n = Node n (ar!(n-1):[ar!k | k<-mayoresDivisores n])

ar = array (1,300) [(i, arbol i) | i<-[1..300]]

caminos :: Int -> [[Int]]

caminos 1 = [[1]]

caminos n = concat [map (n:) (ca!k) | k<-((n-1):mayoresDivisores n)]

ca = array (1,300) [(i, caminos i) | i<-[1..300]]

caminosMinimales :: Int -> [[Int]]

caminosMinimales x = filter (long m) . caminos $ x

where m = minimum . map (length) . caminos $ x

long :: Int -> [Int] -> Bool

long m xs = length xs == m

Responder

Caminos minimales en un árbol numérico

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico