在所有可能的"Subwords"-All possible combinations W/O imports中拆分一个词

Question

我正在尝试通过以下方式在不使用任何导入的情况下获取单词的所有可能组合：

例如...

    Input: Bang

    Output: [['B','ang'], ['Ba','ng'], ['Ban','g'], ['B','a','ng'], ['B','an','g'], ['Ba','n','g'], ['B','a','n','g']]

这个问题困扰了我一段时间，我似乎想不出一个算法来解决这个问题..

下面的代码是我所做的，但这给出了字符串的所有可能组合，但不是我需要的方式。

我试图在 haskell 中实现这个 python 代码，但我无法完成它。基本上是同一个问题，但是 haskell.

中没有循环

下面代码的输出是...

["sun","su","s","un","u","n"]

而不是

[["s","un"],["s","u","n"],["su","n"]]

    -----------------------------------------------------


    substring :: String -> [String]
    substring [] = []
    substring xs = subs xs ++ substring (tail xs)
            where
               subs xs = foldl step [] xs
               step [] a = [[a]]
               step acc a = (head acc ++ [a]) : acc

    ---------------EXAMPLES OF EXPECTED RESULTS BELOW----------------------------------
    Input: Bang
    Output: [['B','ang'], ['Ba','ng'], ['Ban','g'], ['B','a','ng'], ['B','an','g'], ['Ba','n','g'], ['B','a','n','g']]

    Input: Sun
    Output: [["s","un"],["s","u","n"],["su","n"]]

Answer 1

递归在这里提供帮助。假设我们有一个非空列表 x : xs。我们想知道subString (x : xs)。我们将我们的解决方案递归地应用于 xs，因此 subString xs 是 xs 的所有解决方案的列表。然而，我们仍然有那首单曲 x。 x : xs 的解决方案中有两种方法可以恢复 x，它涵盖了 subString (x : xs) 的整个解决方案集：

将 x 带回而不将其附加到其邻居。如果我们有 x : xs = "Bang"，那么 x 将是 'B'，xs 将是 "ang"，而 subString "ang" 将是 [["ang"],["an","g"],["a","ng"],["a","n","g"]]。这是由 [[x] : u | u <- subString xs] 完成的。这里 u 是一个字符串列表，例如 ["a","ng"]。由于 x 是一个字符，我们必须将其转换为字符串，这是通过 [x] 完成的，通过 [x] : u 将其附加到列表的头部，因此 ["B","a","ng"]。列表理解将对 subString xs 中的所有元素执行此操作。
带回 x 并将其附加到它的邻居。 subString xs 的任意解看起来像 u : us。我们想将 x 附加到 u : us 的第一个元素，即 u。所以x : u。例如 u : us = ["a","n","g"] 所以 u 将是 "a" 而 us 将是 ["n","g"]。将 'B' 附加到 "a" 由 'B' : "a" 完成，将得到 "Ba"。我们必须将 "Ba 放回列表中，以便 (x : u) : us。列表 comp[rehension 看起来像 [(x : u) : us | (u : us) <- subString xs].

我们还剩下一个字符串的情况。我们写 [x] 来表示 x 是单个字符。所以 subString [x] 将是 [[[x]]]。

我们必须将解决方案结合在一起，所以

subString :: String -> [[String]]
subString   [x]    = [[[x]]]
subString (x : xs) = [(x : u) : us | (u : us) <- subString xs] ++ [[x] : u | u <- subString xs]

例子

*Main> subString "Bang"
[["Bang"],["Ban","g"],["Ba","ng"],["Ba","n","g"],["B","ang"],["B","an","g"],["B","a","ng"],["B","a","n","g"]]

Answer 2

请注意，您尝试的类型签名是错误的。您想要子词拆分的所有组合，这是一个字符串列表，但您的类型只是一个字符串列表。

这会起作用：

onHead :: (a -> a) -> [a] -> [a]
onHead _ [] = []
onHead f (x:xs) = f x:xs

combos :: [a] -> [[[a]]]
combos [] = [[]]
combos [x] = [[[x]]]
combos (x:xs) = [([x]:), onHead (x:)] <*> combos xs

onHead 应该是不言自明的：在列表的头部执行给定的功能。 combos 递归如下：字符串的子词是其尾部的子词，每种都有两种可能性：头部是它自己的子词，或者它附加到第一个子词的开头。

更新：这是另一种（IMO 清洁器）方法：

combos :: Foldable t => t a -> [[[a]]]
combos = foldr (concatMap . go) [[]]
  where go x l = ([x]:l):case l of
          [] -> []
          h:t -> [(x:h):t]

它使用与上述相同的技术，只是实现更简洁。

在所有可能的"Subwords"-All possible combinations W/O imports中拆分一个词

Splitting a word in all possible "Subwords"-All possible combinations W/O imports

recursion

haskell

haskell-platform