0votos

Subsecuencias monotonicas crecientes en C en Haskell

por josejuan hace 6 años

No me gusta que se exija sin razón un lenguaje concreto. Se puede resolver fácilmente usando LPI, con sólo exigir que para dos índices i<j debe ser Ai<Aj (u otra según monotonía). Mi función permite obtener la subsecuencia más larga de cualquier tipo de monotonía (creciente, nocreciente, decreciente y nodecreciente).

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
-- Usando GLPK, http://www.gnu.org/software/glpk/  
import Data.List  
import Control.Monad  
import Data.LinearProgram  
import Data.LinearProgram.GLPK  
import qualified Data.Map as M  
 
{-- 
 
  Dada una secuencia de valores 
   
       Q1 Q2 Q3 ... QN 
   
  piden obtener otra secuencia 
   
       Q(i1) Q(i2) ... Q(iM) 
   
  con 
   
       iu < iv para todo i,v 
   
  (y obviamente M <= N) tal que dicha secuencia resultante sea 
  monótona y tenga la mayor longitud posible (la menor es 
  trivial). 
   
  Por ejemplo, si tenemos la secuencia 
   
      10 20 30 5 40 50 
   
  se trata únicamente de excluir al 5 para obtener la más larga 
  secuencia monótona creciente estrictamente. 
   
  Si pidieran la decreciente, entonces las posibles soluciones 
  serían 
   
          10 5 
          20 5 
          30 5 
   
  Se puede resolver con programación lineal entera de forma trivial. 
   
  Las incógnitas serán la pertenencia o no (1 o 0) de cada coeficiente en 
  la secuencia de destino. 
   
          Ai 
   
  Entonces, la función de maximización será que haya el mayor número de 
  incógnitas puestas a 1, es decir 
   
   
     MAX: suma Ai 
   
  Según se desee un tipo de monotonía u otro, la restricción será la 
  siguiente. 
   
  Debe ser 
   
       Ai + Aj <= 1  para cada i,j 
   
  tal que (y según criterio) 
   
    Monótona no creciente:               Qi <  Qj 
    Monótona estrictamente creciente:    Qi >= Qj 
    Monótona no decreciente:             Qi >  Qj 
    Monótona estrictamente decreciente:  Qi <= Qj 
      
--}  
 
 
 
-- Sólo por poner nombres a las ordenaciones monotónicas 
data MonotonicType = Increasing | NonIncreasing | Decreasing | NonDecreasing deriving Show 
 
 
 
-- Genera el problema 
largestMonotonic :: MonotonicType -> [Int] -> LP Int Int 
largestMonotonic monotonicType q = execLPM $ problem 
  where problem = do setDirection Max 
                     mapM_ (\(i, j) -> leqTo (varSum [i, j]) 1) restrictedPairs 
                     setObjective $ linCombination $ [(1, i-1) | i <- [1..n]] 
                     mapM_ (\v -> setVarKind v BinVar) [0..n-1] 
        n = length q 
        restrictedPairs = [(i, j) | i <- [0..n-1], j <- [i+1..n-1], orderType monotonicType i j] 
        orderType NonIncreasing i j = q!!i <  q!!j 
        orderType Increasing    i j = q!!i >= q!!j 
        orderType NonDecreasing i j = q!!i >  q!!j 
        orderType Decreasing    i j = q!!i <= q!!j 
                    
 
 
-- Wrapper suponiendo que siempre hay solución (aquí siempre)  
largestMonotonicSolver :: MonotonicType -> [Int] -> IO [Int] 
largestMonotonicSolver monotonicType q = do  
  (_, Just (_, m)) <- glpSolveVars (mipDefaults { msgLev = MsgErr }) $ largestMonotonic monotonicType q 
  return $ map (q!!) $ map fst. M.toList. M.filter (==1) $ m  
 
 
 
-- Helper para generar todos los tipos de monotonía: 
allLargestMonotonic q = mapM_ (\t -> do r <- largestMonotonicSolver t q 
                                        print (t, r)) [NonIncreasing, Increasing, NonDecreasing, Decreasing] 
 
 
{-- 
 
  Ejemplo de uso: 
 
  *Main> allLargestMonotonic [5, 3, 6, 7, 1, 2, 7, 9, 3, 3] 
  (NonIncreasing,[5,3,3,3]) 
  (Increasing,[5,6,7,9]) 
  (NonDecreasing,[5,6,7,7,9]) 
  (Decreasing,[5,3,1]) 
 
  *Main> allLargestMonotonic [5, 0, 9, 6, 1, 12, 3, 7, 2, 5, 0, 9, 6, 1, 12, 3, 7, 2] 
  (NonIncreasing,[9,6,3,3,2]) 
  (Increasing,[0,1,2,5,6,7]) 
  (NonDecreasing,[0,1,3,5,6,7]) 
  (Decreasing,[9,7,6,3,2]) 
 
--} 
1 comentario
0votos

Escrito por josejuan hace 6 años

"iu < iv para todo i,v"

obviamente es

iu < iv para todo u < v


(puede haber otros gazapos por ahí, pero creo se entiende)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.