How to find all possible ways to divide a string into n slices without recursion?

Question

I need to write a function that receives a string and the number of groups, and then returns all the possible slicing options.

i.e. for func('hello', 3):

[['h', 'e', 'llo'], ['h', 'el', 'lo'], ['h', 'ell', 'o'], ['he', 'll', 'o'], ['he', 'l', 'lo'], ['hel', 'l', 'o']]

How can I do this without using recursion? This is supposed to be possible only using loops and lists.

This is similar to a "divide balls into bins" problem, but in this case it's different because the order of objects never changes, just the slicing.

This is the code I currently have:

def divide_into_two(word):
    list_of_divs = []
    for i in range(1, len(word)):
        list_of_divs.append([word[0:i], word[i:len(word)]])

    return list_of_divs

It only divides a word into two groups. I figured we need some kind of inner loop to keep dividing it in case it's more groups, but I'm not sure how to do it.

Answer 1

Using itertools.combinations to pick indices of where to cut the string:

from itertools import combinations

def func(s, n):
    return [[s[i:j] for i, j in zip([None, *cuts], [*cuts, None])]
            for cuts in combinations(range(1, len(s)), n-1)]

Result of func('hello', 3):

[['h', 'e', 'llo'], ['h', 'el', 'lo'], ['h', 'ell', 'o'], ['he', 'l', 'lo'], ['he', 'll', 'o'], ['hel', 'l', 'o']]

An alternative solution, starting with all single-slice divisions (i.e., just the whole string), then computing two-slice divisions, then three-slice divisions, etc. Done by always splitting the last slice into two, in all ways that allow the desired remaining number of splits:

def func(s, n):
    divs = [[s]]
    for i in range(n-1):
        divs = [[*keep, last[:j], last[j:]]
                for *keep, last in divs
                for j in range(1, len(last)-n+i+2)]
    return divs