0votos

Subsecuencias monotonicas crecientes en C en Haskell

por josejuan hace 6 años

Por fuerza bruta en Haskell. Los nombres un poco largos para mis gusto pero bueno...

El programa consiste en escribir un programa que encuentre la subsecuencia monot ́onica creciente de mayor taman ̃o dado una lista de nu ́meros diferentes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
-- Dado un chequeador de monoticidad y una secuencia, devuelve la subsecuencia más larga posible 
largestMonotonicSequence :: Ord a => (a -> a -> Bool) -> [a] -> [a] 
largestMonotonicSequence monotonicityOrderChecker = 
  reverse . head . sortBy (flip (compare.length).length) . gen [] 
  where gen xss [] = xss 
        gen xss (y:ys) = gen (xss ++ [[y]] ++ add y xss) ys 
        add y xss = map (y:) $ filter (monotonicityOrderChecker y.head) xss 
 
 
 
 
 
 
-- Helper para calcularlas todas: 
allLargestMonotonicSequences :: Ord a => [a] -> [(String, [a])] 
allLargestMonotonicSequences xs = map (second $ flip largestMonotonicSequence xs) [("Decreasing"   , (< )) 
                                                                                  ,("NonDecreasing", (>=)) 
                                                                                  ,("NonIncreasing", (<=)) 
                                                                                  ,("Increasing"   , (> ))] 
 
-- Helper para imprimir todas: 
printAllLargestMonotonicSequences :: (Ord a, Show a) => [a] -> IO () 
printAllLargestMonotonicSequences = mapM_ format . allLargestMonotonicSequences 
  where format (mononicityType, sequence) = putStrLn $ mononicityType ++ ":\t" ++ show sequence 
 
 
{-- 
 
  Ejemplo de uso: 
 
    *Main> printAllLargestMonotonicSequences [2, 1, 4, 3, 4, 3, 6, 5, 7] 
    Decreasing:     [2,1] 
    NonDecreasing:  [2,4,4,6,7] 
    NonIncreasing:  [4,3,3] 
    Increasing:     [2,3,4,6,7] 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.