Styjun

I am trying to get all the possible combinations of a word in the following manner WITHOUT using any imports:

For example...

 Input: Bang

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

This problem has been bothering me for some time and i can't seem to figure out an algorithm to do this..

The code below is what i've done but this gives all the possible combinations of a string but not in the manner that i need.

I tried to implement this python code in haskell but i wasn't able to accomplish it. It basically is the same problem, but you don't have loops in haskell.

Splitting a word into all possible 'subwords' - All possible combinations

The output of the code below is...

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

and not

[["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"]]

Recursion is here to help. Say we have a non-empty list x : xs. We want to know subString (x : xs). We apply our solution recursively to xs, so subString xs is a list of all solutions for xs. However we still have that single x. There are exactly two ways to bring back x in the solution for x : xs which covers for the entire solution set of subString (x : xs):

• Bring x back without attaching it to its neighbor. If we have x : xs = "Bang" then x will be 'B' and xs will be "ang" and subString "ang" will be [["ang"],["an","g"],["a","ng"],["a","n","g"]]. This is done by [[x] : u | u <- subString xs]. Here u is a list of Strings, for example ["a","ng"]. As x is a character we must turn it to a String, this is done by [x], attaching it to the head of the list goes by [x] : u, so ["B","a","ng"]. The list comprehension will do it for all elements in subString xs.


• Bring x back attaching it to its neighbors. An arbitrary solution of subString xs will look like u : us. We want to attach x to the first element of u : us which is u. So x : u. For example u : us = ["a","n","g"] so u will be "a" and us will be ["n","g"]. Attaching 'B' to "a" is done by 'B' : "a" and will give "Ba". We have to put "Ba back in the list so (x : u) : us. The list comp[rehension looks like [(x : u) : us | (u : us) <- subString xs].

We are still left with the case of a String of a single character. We write [x] for that where x is the single character. So subString [x] will be [[[x]]].

We have to join the solutions together so

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

Example

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

Note that the type signature of your attempt is wrong. You want all of the combinations of subword splits, which is a list of list of strings, but your type is just a list of list of strings.

This will work:

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 should be self-explanatory: perform the given function on the head of a list. combos recurses as follows: the subwords of a string are the subwords of its tail, with two possibilities for each: either the head is its own subword, or it's tacked onto the beginning of the first subword.

Update: Here's another (IMO cleaner) approach:

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

It's using the same technique as above, just with a cleaner implementation.