Create possible combinations of specific size

Question

The string/list is e.g. 'foobar'. I need to break this up in all possible combinations where the number of groups is n, e.g. 3.

This would give me e.g.

['foo', 'ba',  'r']
['f',  'ooba', 'r']
['fo', 'oo',   'bar']
['f',  'o',    'obar']

etc

What is the best algorithm to create all the possible combinations?

Answer 1

Sounds like a job for itertools:

from itertools import combinations

def compositions(s,k):
    n = len(s)
    for c in combinations(range(1,n),k-1):
        yield [s[i:j] for i,j in zip((0,)+c,c+(n,))]

The way it works is that the combinations part yields tuples which consist of possible cut points. For example (with s = "foobar" and k = 3) (2,4) is one of the tuples. Breaking at these indices should yield ["fo","ob","ar"] which corresponds to [s[0:2],s[2,4],s[4,6]] the expression zip((0,)+c,c+(n,)) in this case is the same as zip((0,2,4),(2,4,6)) hence iterating over it has the effect of iterating over the the successive pairs of indices for the successive slices.

For example,

>>> for c in compositions("foobar",3): print(c)

['f', 'o', 'obar']
['f', 'oo', 'bar']
['f', 'oob', 'ar']
['f', 'ooba', 'r']
['fo', 'o', 'bar']
['fo', 'ob', 'ar']
['fo', 'oba', 'r']
['foo', 'b', 'ar']
['foo', 'ba', 'r']
['foob', 'a', 'r']

I chose the name "compositions" since you are essentially talking about compositions in combinatorics. My algorithm was based on the proof in the linked article that the number of compositions of n items into k pieces is C(n-1,k-1).

Answer 2

Here is a simple recursion

def split(s, n):
    def rec_split(i, s, n):
        ans = []

        if n == 1:
            ans.append([s[i:]])
            return ans

        for j in range(i+1, len(s)):
            head = s[i:j]
            tails = rec_split(j, s, n-1)
            for tail in tails:
                ans.append([head] + tail)
        return ans

    return rec_split(0, s, n)

for e in split("foobar", 3):
    print(e)

# ['f', 'o', 'obar']
# ['f', 'oo', 'bar']
# ['f', 'oob', 'ar']
# ['f', 'ooba', 'r']
# ['fo', 'o', 'bar']
# ['fo', 'ob', 'ar']
# ['fo', 'oba', 'r']
# ['foo', 'b', 'ar']
# ['foo', 'ba', 'r']
# ['foob', 'a', 'r']

rec_split returns all partitions of s in n parts from the i-th index onward