Strings aus Matrix

Question

Ich bin fest mit meinen Hausaufgaben Aufgabe, jemand helfen, bitte ..

Hier ist die Aufgabe: Suche alle möglichen Partitionen der Zeichenfolge in Worte einiger Wörterbuch

Und hier ist wie ich versuche, es zu tun: ich dynamische Programmierkonzept verwenden Matrix zu füllen und dann bin ich stecken mit, wie zum abrufen von Daten aus es

-- Task5_2 
retrieve :: [[Int]] -> [String] -> Int -> Int -> Int -> [[String]] 
retrieve matrix dict i j size 
    | i >= size || j >= size = [] 
    | index /= 0 = [(dict !! index)]:(retrieve matrix dict (i + sizeOfWord) (i + sizeOfWord) size) ++ retrieve matrix dict i (next matrix i j) size 
    where index = (matrix !! i !! j) - 1; sizeOfWord = length (dict !! index) 


next matrix i j 
    | j >= (length matrix) = j 
    | matrix !! i !! j > 0 = j 
    | otherwise = next matrix i (j + 1) 

getPartitionMatrix :: String -> [String] -> [[Int]] 
getPartitionMatrix text dict = [[ indiceOfWord (getWord text i j) dict 1 | j <- [1..(length text)]] | i <- [1..(length text)]] 

-------------------------- 
getWord :: String -> Int -> Int -> String 
getWord text from to = map fst $ filter (\a -> (snd a) >= from && (snd a) <= to) $ zip text [1..] 


indiceOfWord :: String -> [String] -> Int -> Int 
indiceOfWord _ [] _ = 0 
indiceOfWord word (x:xs) n 
    | word == x = n 
    | otherwise = indiceOfWord word xs (n + 1) 


-- TESTS 
dictionary = ["la", "a", "laa", "l"] 
string = "laa" 
matr = getPartitionMatrix string dictionary 
test = retrieve matr dictionary 0 0 (length string) 

Answer 1

Hier ist ein Code, der das tun, was Sie verlangen. Es funktioniert nicht genau wie Ihre Lösung, sollte aber so schnell funktionieren, wenn (und nur wenn) beide unserer Wörterbuch-Lookups verbessert wurden, um Versuche zu verwenden, wie es vernünftig wäre. Wie es ist glaube ich es ein bisschen schneller als die Lösung sein kann:

module Partitions (partitions) where 
import Data.Array 
import Data.List 

data Branches a = Empty | B [([a],Branches a)] deriving (Show) 

isEmpty Empty = True 
isEmpty _  = False 

flatten :: Branches a -> [ [ [a] ] ] 
flatten Empty = [] 
flatten (B []) = [[]] 
flatten (B ps) = concatMap (\(word, bs) -> ...) ps 

type Dictionary a = [[a]] 

partitions :: (Ord a) => Dictionary a -> [a] -> [ [ [a] ] ] 
partitions dict xs = flatten (parts ! 0) 
    where 
     parts = listArray (0,length xs) $ zipWith (\i ys -> starting i ys) [0..] (tails xs) 
     starting _ [] = B [] 
     starting i ys 
      | null words = ... 
      | otherwise = ... 
      where 
      words = filter (`isPrefixOf` ys) $ dict 
      go word = (word, parts ! (i + length word)) 

Es funktioniert wie folgt: An jeder Position der Zeichenfolge suchen es alle möglichen Wörter von dort im Wörterbuch Start und wertet auf einen Branches , das ist entweder eine Sackgasse (Empty) oder eine Liste von Wortpaaren und allen möglichen Fortsetzungen danach, wobei diejenigen Wörter verworfen werden, die nicht fortgesetzt werden können.

Dynamische Programmierung geben Sie das Bild ein, um alle Möglichkeiten ab einem bestimmten Index in einem Lazy-Array aufzuzeichnen. Beachten Sie, dass der Knoten gebunden ist: Wir berechnen parts mit starting, die parts verwendet, um zu suchen, welche Fortsetzungen von einem bestimmten Index möglich sind. Dies funktioniert nur, weil wir nur nach Indizes suchen, die starting berechnen und starting nicht parts für den letzten Index verwenden.

Um die Liste der Partitionen aus diesem Branches-Datentyp abzurufen, ist dies analog zur Auflistung aller Pfade in einem Baum.

EDIT: Ich entfernte einige entscheidende Teile der Lösung, um den Fragesteller für sich selbst suchen zu lassen. Obwohl das mit etwas Nachdenken nicht zu schwer sein sollte. Ich werde sie wahrscheinlich später mit einer etwas aufgeräumten Version zurückstellen.