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

user_12965153 0
Viewed 133

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.

for-loop list python loops
3 Answers

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
user_142653730

You can use more itertools.

from more_itertools import partitions

def divide_into_parts(word, parts):
    result = []
    for p in partitions(word):
        if len(p) == parts:
            result.append([''.join(s) for s in p])
    return result

Result

divide_into_parts('hello', 3)

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

Here is a possible solution:

from itertools import combinations

def slicings(s, g):
    for c in combinations(range(1, len(s)), g - 1):
        yield [s[start:end] for start, end in zip((0,) + c, c + (len(s),))]

You can now do whatever you want with you generator of slicings:

for slicing in slicings('hello', 3):
    print(slicing)

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

In these cases, it's better to generate things as you need them (use yield instead of return) because there could be an exponential number of results depending on your specific case.

user_52961060
Related