时间戳

首页 > 解决方案 > 在所有可能的“子词”中拆分一个词 - 所有可能的组合 W/O 导入

haskell - 在所有可能的“子词”中拆分一个词 - 所有可能的组合 W/O 导入

问题描述

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

例如...

    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中没有循环。

将一个词拆分为所有可能的“子词”——所有可能的组合

下面代码的输出是......

["太阳","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"]]

标签： haskellrecursionhaskell-platform

解决方案

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

这将起作用：

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]

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

推荐阅读