從矩陣

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數據類型檢索分區列表類似於樹中所有路徑的列表。

編輯：我刪除了解決方案的一些關鍵部分，以便讓提問者自己搜索。雖然這不應該太難以完成一些想法。我可能會在稍後將它們稍微清理一些。