从矩阵

Question

我坚持我的家庭作业任务，有人帮助，请检索串..

这里的任务： 查找字符串的所有可能划分成一些字典中的单词

这里是怎么我试图做到这一点： 我用动态规划理念，以填补矩阵，然后我坚持了如何检索数据从它

-- 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

这里是做什么你问的代码。它不能像你的解决方案一样工作，但是如果（并且只有）我们的字典查找得到改进才能使用尝试，这应该是合理的。由于这是我认为它可能比你的解决方案快了一下：

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)) 

它的工作原理是这样的：在字符串的每个位置，它可以搜索所有可能的话从那里开始的字典和计算结果为Branches ，或者是死路一条（Empty）或者一个单词对以及所有可能的后续单词列表，丢弃那些无法继续的单词。

动态编程输入图片以记录从懒惰数组中的给定索引开始的所有可能性。请注意，结是并列的：我们通过使用starting来计算parts，它使用parts来查找哪个延续可能来自给定的索引。这仅适用，因为我们只在一个starting正在计算之后查找索引，而starting不会使用parts作为最后一个索引。

从这个Branches数据类型检索分区列表类似于树中所有路径的列表。

编辑：我删除了解决方案的一些关键部分，以便让提问者自己搜索。虽然这不应该太难以完成一些想法。我可能会在稍后将它们稍微清理一些。