1votos

Minimal Superpermutations en Haskell

por josejuan hace 6 años

Usando una búsqueda en anchura (A*) también puede encontrarse fácilmente, la pena es que el rendimiento también es penoso. No es extraño, porque nadie ha encontrado aún una solución (eficiente) al problema.

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
import Data.List 
import qualified Data.Heap as Heap 
import Data.Maybe 
import System.Environment 
 
minPermutations abc = solve1 initialHeap 
  where 
    solve1 = solve2 . fromJust . Heap.view 
    solve2 (e@(s, (o, ps)), h) = if null ps then (s, o) 
                                            else solve1 $ foldl (flip Heap.insert) h $ grow e 
    grow (s, (o@(c:_), ps)) = map (\o' -> (s + 1, (o', filter (not.flip isInfixOf o') ps))) [x:o | x <- abc, x /= c] 
     
    initialHeap = Heap.insert (length abc, (abc, permutations abc))        -- Nuestro heap está ordenado por 
                              (Heap.empty :: Heap.MinPrioHeap Int          -- longitud de la cadena a buscar 
                                                              ( String     -- y almacena la cadena a buscar 
                                                              , [String])) -- y las permutaciones que no contiene 
 
main = getArgs >>= print . minPermutations . head 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.