0votos

Minimal Superpermutations en Haskell

por josejuan hace 6 años

El algoritmo trivial (concatenar permutaciones hasta terminar) puede hacerse en tiempo casi lineal O(p), lo que pasa que como el número de permutaciones es p=n! resulta que el coste práctico respecto el nº de símbolos es O(n!), aún así puede mejorarse mucho este algoritmo. La pena es que no sirve (ver A007489).

Obtener una cadena de longitud mínima que contenga todas las permutaciones de n símbolos.

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
122
123
124
125
126
127
import KTrie -- ¡¿ no he encontrado una implementación genérica de Trie en Haskell ?! (la que he hecho está abajo) 
import qualified Data.List as L 
import qualified Data.Map as M 
import Prelude hiding (null, lookup) 
import System.Environment (getArgs) 
 
minp :: Ord a => [a] -> [a] 
minp abc = solve (L.reverse $ head perms) (foldl (flip insert) empty (L.tail perms)) 
  where n = length abc 
        perms = L.permutations abc 
        solve r ps = if null ps then r 
                                else solve ((L.reverse $ L.drop (n - i) p') ++ r) (remove p' ps) -- la primera permutación de máxima longitud que haya ¡¿?! 
                     where (p, i) = head [(p, i) | i <- [1..n - 1]                               -- tomaremos sufijos del resultado actual de tamaños 1..n-1 
                                                 , let p = L.reverse $ L.take (n - i) r          -- como van invertidos 
                                                 , contains p ps]                                -- que aún esté en la lista de permutaciones pendientes 
                           p' = fullDeepLookup p ps                                              -- un representante 
 
 
main = getArgs >>= print . length . minp . flip take ['A'..'Z'] . read . head 
 
 
 
 
 
 
 
-- Módulo: KTrie.hs ------------------------- 
--   permite clasificar buscar rápidamente por prefijos 
-- trie implementation for generic keys (no data into trie) 
module KTrie ( contains 
             , empty 
             , fullDeepLookup 
             , insert 
             , lookup 
             , null 
             , remove 
             , toList 
             , Trie ) where 
 
import qualified Data.Map as M 
import Data.Map ((!)) 
import Prelude hiding (null, lookup) 
import Data.Maybe (fromMaybe) 
 
data Trie a = Trie (M.Map a (Trie a)) deriving Show 
 
-- Trie vacío 
empty :: Ord a => Trie a 
empty = Trie M.empty 
 
-- ¿Trie vacío? 
null :: Ord a => Trie a -> Bool 
null (Trie m) = M.null m 
 
-- inserta la rama indicada 
insert :: Ord a => [a] -> Trie a -> Trie a 
insert [] t = t 
insert (x:xs) (Trie m) = Trie m' 
  where m' = M.alter t' x m 
        t' = Just . insert xs . fromMaybe empty 
 
-- borra la rama indicada por el mayor prefijo de la cadena indicada 
remove :: Ord a => [a] -> Trie a -> Trie a 
remove [] t = t 
remove (x:xs) (Trie m) = Trie m' 
  where m' = M.alter t x m 
        t v = case v of 
              Nothing -> Nothing 
              Just t' -> if null t'' then Nothing 
                                     else Just t'' 
                         where t'' = remove xs t' 
 
-- indica si contiene la rama indicada 
contains :: Ord a => [a] -> Trie a -> Bool 
contains [] _ = True 
contains (x:xs) (Trie m) = case M.lookup x m of 
                           Just t  -> contains xs t 
                           Nothing -> False 
 
-- devuelve la subrama indicada por el prefijo, 
-- si no existe la rama indicada por el prefijo da error 
lookup :: Ord a => [a] -> Trie a -> Trie a 
lookup [] t = t 
lookup (x:xs) t@(Trie m) = lookup xs $ M.findWithDefault t x m 
 
-- dado un prefijo devuelve un representante cualquiera hasta alguna hoja 
fullDeepLookup :: Ord a => [a] -> Trie a -> [a] 
fullDeepLookup xs t = xs ++ grow (lookup xs t) 
  where grow (Trie m) = if M.null m then [] 
                                    else h : grow (m!h) 
                        where h = head $ M.keys m 
 
toList :: Ord a => Trie a -> [[a]] 
toList (Trie m) = if M.null m then [[]] else concatMap (\k -> map (k:) $ toList (m!k)) $ M.keys m 
 
{-- 
 
Tiempos de ejecución y memoria (en Kbytes) para cada n=1..10 
 
==== n = 2 
0:00.02, 1692 
==== n = 3 
0:00.02, 1720 
==== n = 4 
33 
0:00.03, 1784 
==== n = 5 
153 
0:00.03, 2192 
==== n = 6 
873 
0:00.03, 2472 
==== n = 7 
5913 
0:00.06, 5696 
==== n = 8 
46233 
0:00.48, 31004 
==== n = 9 
409113 
0:05.18, 260412 
==== n = 10 
4037913 
1:05.18, 2820420 
--} 
7 comentarios
0votos

Escrito por jneira hace 6 años

Podrias extenderte en lo de "no sirve (ver A007489)". Supongo que te refieres a la secuencia http://oeis.org/A007489 y el algoritmo si que la sigue...
0votos

Escrito por josejuan hace 6 años

Perdón tienes razón, es la A180632, que me he equivocado.

Afirmas que sigue la A007489, ¿podrías demostrarlo?.

;D
0votos

Escrito por jneira hace 6 años

"y el algoritmo si que la sigue..." hasta n=10, se me olvido añadir :-P
Tal vez la implementacion de trie que buscabas podria ser: http://hackage.haskell.org/packages/archive/bytestring-trie/0.1.4/doc/html/Data-Trie.html ??
0votos

Escrito por josejuan hace 6 años

Si la sigue hasta n=10 ¿porqué A180632 sólo llega a 4? (por otro lado, aunque el algoritmo arroje el mismo resultado que una búsqueda por fuerza bruta, no quiere decir que el algoritmo sea correcto para cierto n).

En cuanto a Trie, algunos pesos pesados de Haskell han tenido la amabilidad de responderme a la pregunta en stackoverflow.

Me quedo con list-tries por ser fácil (de hecho, coincide mi implementación con la de éste módulo) y con TrieMap, una implementación más genérica y refinada. Me quedo con ellas porque la primera es práctica en muchos casos y la segunda puede venir bien para ciertas estructuras más complejas (ej. hacer un trie de árboles).

En cuanto a Data-Trie tiene la pega de que la claves son ByteStrings y por tanto debes hacer tú la conversión.
0votos

Escrito por josejuan hace 6 años

"por otro lado, aunque el algoritmo arroje el mismo resultado que una búsqueda por fuerza bruta, no quiere decir que el algoritmo sea correcto para cierto n"

Lo explicaré con un ejemplo, si te piden "escriba un algoritmo que encuentre los primeros 5 números primos", ¿sería correcto escribir "lookupPrime n = [2, 3, 5, 7, 11]!!n"?.

Pues igual con lo demás, que cierto algoritmo arroje los mismos resultados que otro algoritmo que sabemos da la respuesta correcta, no quiere decir que el primer algoritmo sea correcto ¡aunque en la práctica sería perfectamente válido usarlo!.
0votos

Escrito por jneira hace 6 años

No he analizado el algoritmo pero supongo que no es valido por la misma razon que el mio, ¿no?: "a primera permutación de máxima longitud que haya ¡¿?!"
¿Como se podria demostrar que cojas el que cojas de los posibles prefijos el tamaño sea siempre igual (el minimo)? ¿Es imposible o tienes alguna idea de por donde podria ir la demostracion?
0votos

Escrito por josejuan hace 6 años

"por la misma razon que el mio"

Es que el algoritmo es tu algoritmo, yo únicamente he usado una estrategia mucho más eficiente (usar tries).

"¿Como se podria demostrar... ¿Es imposible..."

Yo no lo se, puede que el método sirva, pero ni yo ni otros mucho más preparados que yo lo han conseguido, ¿será la cadena mínima?, ...

Suelo utilizar el principio de autoridad como primera aproximación cuando desconozco un problema (sobre todo en matemáticas), aunque después suelo intentar escudriñar y cuestionar (con escasísimos resultados XD XD).

"tienes alguna idea"

No suelo cuestionar resultados matemáticos (el resultado ahora es que no se ha encontrado solución) y estoy seguro de mi incapacidad al respecto; podría escribir aquí algunas ideas, pero (sí, por el principio de autoridad) desisto de antemano a que lleven a buen puerto.

Cosa diferente es encontrar un algoritmo que DEMUESTRE que encuentra la cadena mínima, yo he presentado dos (A* y LPI) pero son ineficientes en la práctica para rastrear n "altos" (aquí alto es n=10).

Aquí si me veo con capacidad (osado de mí) de encontrar variantes o soluciones prácticas para n "altos" (por lo visto encontrar las cadenas para n=6 DEMOSTRADAS, ya se que coinciden con el algoritmo trivial, es un reto importante).

Tendré un tiempo el problema en la cabeza, por si sale algo al estilo del Dick T. Winter. XD XD

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.