Mayores sublistas crecientes

Definir las funciones

   mayoresCrecientes :: Ord a => [a] -> [[a]]
   longitudMayorSublistaCreciente :: Ord a => [a] -> Int

1 2	mayoresCrecientes :: Ord a => [a] -> [[a]] longitudMayorSublistaCreciente :: Ord a => [a] -> Int

tales que

(mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,

     λ> mayoresCrecientes [3,2,6,4,5,1]
     [[3,4,5],[2,4,5]]
     λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
     [[10,22,33,50,60,80],[10,22,33,41,60,80]]
     λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
     [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
     λ> length (head (mayoresCrecientes (show (2^70))))
     5

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

[[3,4,5],[2,4,5]]

λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]

[[10,22,33,50,60,80],[10,22,33,41,60,80]]

λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]

λ> length (head (mayoresCrecientes (show (2^70))))

(longitudMayorSublistaCreciente xs) es el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

     λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
     3
     λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
     6
     λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
     6
     λ> longitudMayorSublistaCreciente [1..2000]
     2000
     λ> longitudMayorSublistaCreciente [2000,1999..1]
     1

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

λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]

λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

λ> longitudMayorSublistaCreciente [1..2000]

2000

λ> longitudMayorSublistaCreciente [2000,1999..1]

Soluciones

[schedule expon=’2017-06-08′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 08 de junio.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-06-08′ at=»06:00″]

import Data.List (nub, sort, subsequences)
import Data.Array

-- 1ª definición de mayoresCrecientes
-- ==================================

mayoresCrecientes1 :: Ord a => [a] -> [[a]]
mayoresCrecientes1 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes xs
        m   = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes [3,2,5]
--    [[],[3],[2],[5],[3,5],[2,5]]
sublistasCrecientes :: Ord a => [a] -> [[a]]
sublistasCrecientes xs =
  [ys | ys <- subsequences xs
      , esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por
-- ejemplo,  
--    esCreciente [2,3,5]  ==  True
--    esCreciente [2,3,1]  ==  False
--    esCreciente [2,3,3]  ==  False
esCreciente :: Ord a => [a] -> Bool
esCreciente (x:y:zs) = x < y && esCreciente (y:zs)
esCreciente _        = True

-- 2ª definición de mayoresCrecientes
-- ==================================

mayoresCrecientes2 :: Ord a => [a] -> [[a]]
mayoresCrecientes2 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes2 xs
        m   = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes2 [3,2,5]
--    [[3,5],[3],[2,5],[2],[5],[]]
sublistasCrecientes2 :: Ord a => [a] -> [[a]]
sublistasCrecientes2 []  = [[]]
sublistasCrecientes2 (x:xs) =
  [x:ys | ys <- yss, null ys || x < head ys] ++ yss
  where yss = sublistasCrecientes2 xs

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

--    λ> length (head (mayoresCrecientes1 (show (2^70))))
--    5
--    (10.93 secs, 1,958,822,896 bytes)
--    λ> length (head (mayoresCrecientes2 (show (2^70))))
--    5
--    (0.02 secs, 0 bytes)

-- 1ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente1 =
  length . head . mayoresCrecientes1

-- 2ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente2 =
  length . head . mayoresCrecientes2

-- Comparación de eficiencia:
--    λ> longitudMayorSublistaCreciente1 (show (2^70))
--    5
--    (10.78 secs, 1,969,452,328 bytes)
--    λ> longitudMayorSublistaCreciente2 (show (2^70))
--    5
--    (0.02 secs, 0 bytes)

-- 3ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente3 xs =
  longitudSCM xs (sort (nub xs))
  
-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e
-- ys. Por ejemplo, 
--   longitudSCM "amapola" "matamoscas" == 4
--   longitudSCM "atamos" "matamoscas"  == 6
--   longitudSCM "aaa" "bbbb"           == 0
longitudSCM :: Eq a => [a] -> [a] -> Int
longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)
  where n = length xs
        m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es la longitud de la SCM de los i
-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizLongitudSCM "amapola" "matamoscas")
--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,
--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,
--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]
-- Gráficamente,
--       m a t a m o s c a s
--    [0,0,0,0,0,0,0,0,0,0,0,
-- a   0,0,1,1,1,1,1,1,1,1,1,
-- m   0,1,1,1,1,2,2,2,2,2,2,
-- a   0,1,2,2,2,2,2,2,2,3,3,
-- p   0,1,2,2,2,2,2,2,2,3,3,
-- o   0,1,2,2,2,2,3,3,3,3,3,
-- l   0,1,2,2,2,2,3,3,3,3,3,
-- a   0,1,2,2,3,3,3,3,3,4,4]
matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int
matrizLongitudSCM xs ys = q
  where
    n = length xs
    m = length ys
    v = listArray (1,n) xs
    w = listArray (1,m) ys
    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
      where f 0 _ = 0
            f _ 0 = 0
            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)
                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))
  
-- Comparación de eficiencia
-- -------------------------

--    λ> longitudMayorSublistaCreciente2 [1..22]
--    22
--    (19.63 secs, 2,271,936,784 bytes)
--    λ> longitudMayorSublistaCreciente3 [1..22]
--    22
--    (0.01 secs, 0 bytes)

-- 4ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente4 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente4 xs =
  maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n
-- tal que el valor i-ésimo es la longitud de la sucesión más largar que
-- termina en el elemento i-ésimo de xs. Por ejemplo, 
--    λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]
--    array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]
vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int
vectorlongitudMayorSublistaCreciente xs = v
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        n = length xs
        w = listArray (1,n) xs
        f 1 = 1
        f i | null ls   = 1
            | otherwise = 1 + maximum ls
          where ls = [v ! j | j <- [1..i-1], w ! j < w ! i]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

import Data.List (nub, sort, subsequences)

import Data.Array

-- 1ª definición de mayoresCrecientes

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

mayoresCrecientes1 :: Ord a => [a] -> [[a]]

mayoresCrecientes1 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes xs

m = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes [3,2,5]

-- [[],[3],[2],[5],[3,5],[2,5]]

sublistasCrecientes :: Ord a => [a] -> [[a]]

sublistasCrecientes xs =

[ys | ys <- subsequences xs

, esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por

-- ejemplo,

-- esCreciente [2,3,5] == True

-- esCreciente [2,3,1] == False

-- esCreciente [2,3,3] == False

esCreciente :: Ord a => [a] -> Bool

esCreciente (x:y:zs) = x < y && esCreciente (y:zs)

esCreciente _ = True

-- 2ª definición de mayoresCrecientes

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

mayoresCrecientes2 :: Ord a => [a] -> [[a]]

mayoresCrecientes2 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes2 xs

m = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes2 [3,2,5]

-- [[3,5],[3],[2,5],[2],[5],[]]

sublistasCrecientes2 :: Ord a => [a] -> [[a]]

sublistasCrecientes2 [] = [[]]

sublistasCrecientes2 (x:xs) =

[x:ys | ys <- yss, null ys || x < head ys] ++ yss

where yss = sublistasCrecientes2 xs

-- Comparación de eficiencia

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

-- λ> length (head (mayoresCrecientes1 (show (2^70))))

-- 5

-- (10.93 secs, 1,958,822,896 bytes)

-- λ> length (head (mayoresCrecientes2 (show (2^70))))

-- 5

-- (0.02 secs, 0 bytes)

-- 1ª definición de longitudMayorSublistaCreciente

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

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente1 =

length . head . mayoresCrecientes1

-- 2ª definición de longitudMayorSublistaCreciente

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

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente2 =

length . head . mayoresCrecientes2

-- Comparación de eficiencia:

-- λ> longitudMayorSublistaCreciente1 (show (2^70))

-- 5

-- (10.78 secs, 1,969,452,328 bytes)

-- λ> longitudMayorSublistaCreciente2 (show (2^70))

-- 5

-- (0.02 secs, 0 bytes)

-- 3ª definición de longitudMayorSublistaCreciente

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

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente3 xs =

longitudSCM xs (sort (nub xs))

-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e

-- ys. Por ejemplo,

-- longitudSCM "amapola" "matamoscas" == 4

-- longitudSCM "atamos" "matamoscas" == 6

-- longitudSCM "aaa" "bbbb" == 0

longitudSCM :: Eq a => [a] -> [a] -> Int

longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)

where n = length xs

m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n

-- y m son los números de elementos de xs e ys, respectivamente) tal que

-- el valor en la posición (i,j) es la longitud de la SCM de los i

-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,

-- λ> elems (matrizLongitudSCM "amapola" "matamoscas")

-- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,

-- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,

-- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]

-- Gráficamente,

-- m a t a m o s c a s

-- [0,0,0,0,0,0,0,0,0,0,0,

-- a 0,0,1,1,1,1,1,1,1,1,1,

-- m 0,1,1,1,1,2,2,2,2,2,2,

-- a 0,1,2,2,2,2,2,2,2,3,3,

-- p 0,1,2,2,2,2,2,2,2,3,3,

-- o 0,1,2,2,2,2,3,3,3,3,3,

-- l 0,1,2,2,2,2,3,3,3,3,3,

-- a 0,1,2,2,3,3,3,3,3,4,4]

matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int

matrizLongitudSCM xs ys = q

where

n = length xs

m = length ys

v = listArray (1,n) xs

w = listArray (1,m) ys

q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]

where f 0 _ = 0

f _ 0 = 0

f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)

| otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

-- Comparación de eficiencia

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

-- λ> longitudMayorSublistaCreciente2 [1..22]

-- 22

-- (19.63 secs, 2,271,936,784 bytes)

-- λ> longitudMayorSublistaCreciente3 [1..22]

-- 22

-- (0.01 secs, 0 bytes)

-- 4ª definición de longitudMayorSublistaCreciente

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

longitudMayorSublistaCreciente4 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente4 xs =

maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n

-- tal que el valor i-ésimo es la longitud de la sucesión más largar que

-- termina en el elemento i-ésimo de xs. Por ejemplo,

-- λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]

-- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]

vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int

vectorlongitudMayorSublistaCreciente xs = v

where v = array (1,n) [(i,f i) | i <- [1..n]]

n = length xs

w = listArray (1,n) xs

f 1 = 1

f i | null ls = 1

| otherwise = 1 + maximum ls

where ls = [v ! j | j <- [1..i-1], w ! j < w ! i]

[/schedule]

3 Comentarios

mayoresCrecientes :: Ord a => [a] -> [[a]]
mayoresCrecientes xs = map (reverse.v3) $ filter (\(a,b,c) -> a == t) p
 where p = aux [] xs
       t = (\(a,b,c) -> a) $ maximum p
       v3 = (\(a,b,c) -> c) 
aux ys [] = ys
aux ys (x:zs) = aux (inserta1 x ys) zs
        where inserta1 x [] = [(1,x,[x])]
              inserta1 x ((a,b,c):xs) | x > b = (a,b,c):(a+1,x,x:c):inserta2 x xs
                                      | otherwise = (a,b,c):inserta1 x xs
              inserta2 x [] = []
              inserta2 x ((a,b,c):xs) | x > b = (a,b,c):(a+1,x,x:c):inserta2 x xs
                                      | otherwise = (a,b,c):inserta2 x xs

mayoresCrecientes :: Ord a => [a] -> [[a]]

mayoresCrecientes xs = map (reverse.v3) $ filter (\(a,b,c) -> a == t) p

where p = aux [] xs

t = (\(a,b,c) -> a) $ maximum p

v3 = (\(a,b,c) -> c)

aux ys [] = ys

aux ys (x:zs) = aux (inserta1 x ys) zs

where inserta1 x [] = [(1,x,[x])]

inserta1 x ((a,b,c):xs) | x > b = (a,b,c):(a+1,x,x:c):inserta2 x xs

| otherwise = (a,b,c):inserta1 x xs

inserta2 x [] = []

inserta2 x ((a,b,c):xs) | x > b = (a,b,c):(a+1,x,x:c):inserta2 x xs

| otherwise = (a,b,c):inserta2 x xs

Responder

import Data.Map as M

longitudMayorSublistaCreciente :: Ord a => [a] -> Int
longitudMayorSublistaCreciente xs = fst $ findMax t
  where t = ap xs (fromList [(1,head xs)])
        ap [] y = y
        ap (x:zs) y = ap zs (unionWith min y (M.map (\a -> x) $ mapKeys (+1) $ M.filter (x>) y))

import Data.Map as M

longitudMayorSublistaCreciente :: Ord a => [a] -> Int

longitudMayorSublistaCreciente xs = fst $ findMax t

where t = ap xs (fromList [(1,head xs)])

ap [] y = y

ap (x:zs) y = ap zs (unionWith min y (M.map (\a -> x) $ mapKeys (+1) $ M.filter (x>) y))

mayoresCrecientes :: Ord a => [a] -> [[a]]
mayoresCrecientes xs = selec i j
                  where j = auxi xs
                        i = maximum $ map snd j
                        selec _ [] = []          --La función selec elige los mayores
                        selec y ((a,b):xs) | y==b = a : selec y xs
                                           | otherwise = selec y xs

auxi :: Ord a => [a] -> [([a], Int)]
auxi [] = []             --La función auxi hace la recursión
auxi (x:xs) = subCre x xs ++ auxi xs

subCre :: Ord a => a -> [a] -> [([a], Int)]
subCre x [] = []                --subCre crea las sucesiones crecientes pares para
subCre x z@(y:ys) = aux [x] z   --después comparar y elegir las de mayor longitud
       where aux ys [] = [(reverse ys,length ys)]
             aux p@(x:xs) (y:ys) | x<y = aux (y:p) ys ++ aux p ys
                                 | otherwise = aux p ys

longitudMayorSublistaCreciente :: Ord a => [a] -> Int
longitudMayorSublistaCreciente = maximum . map snd . auxi

mayoresCrecientes xs = selec i j

where j = auxi xs

i = maximum $ map snd j

selec _ [] = [] --La función selec elige los mayores

selec y ((a,b):xs) | y==b = a : selec y xs

| otherwise = selec y xs

auxi :: Ord a => [a] -> [([a], Int)]

auxi [] = [] --La función auxi hace la recursión

auxi (x:xs) = subCre x xs ++ auxi xs

subCre :: Ord a => a -> [a] -> [([a], Int)]

subCre x [] = [] --subCre crea las sucesiones crecientes pares para

subCre x z@(y:ys) = aux [x] z --después comparar y elegir las de mayor longitud

where aux ys [] = [(reverse ys,length ys)]

aux p@(x:xs) (y:ys) | x<y = aux (y:p) ys ++ aux p ys

| otherwise = aux p ys

longitudMayorSublistaCreciente = maximum . map snd . auxi

Mayores sublistas crecientes

Soluciones

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico