Find all string split combinations

Question

I'm looking for a way to get all the string splits combinations from a sentence. For example, for the input sentance :

"I am eating pizza"

I would like to get this output :

[["I", "am", "eating", "pizza"],
["I", "am eating", "pizza"],
["I", "am", "eating pizza"],
["I", "am eating pizza"],
["I am", "eating", "pizza"],
["I am", "eating pizza"],
["I am eating", "pizza"],
["I am eating pizza"]]

I can't find the recursive way of doing this ! Do you have any idea ? This is NOT a duplicate : I am not looking for the whole combinations, only ordered items and always the whole words. Can't find my answer from the alleged duplicate.

Answer 1

subdivide and recur

Here's a way you can do it using a recursive function – and how I approached the design:

• Scan a string s using an index i
• If the index goes out of bounds, return the base result, [[s]], otherwise...
• If a " " is found at the index, subdivide the problem into two parts A and B and merge their results, otherwise advance to the next index.
• Part A: split on this space, prepend word before it to each item in the recursive result.
• Part B: do not split on this space, advance to the next index

# split :: String -> [[String]]
def split (s, i = 0):
  if len(s) == i:
    return [[s]]
  elif s[i] == " ":
           # Part A                                     # Part B
    return [[s[0:i]] + acc for acc in split(s[i + 1:])] + split(s, i + 1)
  else:
    return split(s, i + 1)

print(split("i am eating pizza"))

# [ ['i', 'am', 'eating', 'pizza'], 
# , ['i', 'am', 'eating pizza']
# , ['i', 'am eating', 'pizza']
# , ['i', 'am eating pizza']
# , ['i am', 'eating', 'pizza']
# , ['i am', 'eating pizza']
# , ['i am eating', 'pizza']
# , ['i am eating pizza']
# ]

Answer 2

Thanks to Alfe with his hint with the 2^n combinations.

This is some code, corresponding to his idea.

import itertools
input_string = "I am eating pizza"
split_string = input_string.split(' ')
lst = list(itertools.product([0, 1], repeat=len(split_string) - 1))

res = [] 
for entry in lst:
    round_output = []
    current = split_string[0]
    for i in range(len(entry)):
        if entry[i] == 1:
            current += ' ' + split_string[i+1]
        else:    
            round_output.append(current)
            current = split_string[i+1]
    round_output.append(current)
    res.append(round_output)