Here is a recipe for partitioning a sequence into n groups, based on code by Raymond Hettinger:
import itertools as IT
def partition_into_n(iterable, n, chain=IT.chain, map=map):
"""
Based on http://code.activestate.com/recipes/576795/ (Raymond Hettinger)
Modified to include empty partitions, and restricted to partitions of length n
"""
s = iterable if hasattr(iterable, '__getslice__') else tuple(iterable)
m = len(s)
first, middle, last = [0], range(m + 1), [m]
getslice = s.__getslice__
return (map(getslice, chain(first, div), chain(div, last))
for div in IT.combinations_with_replacement(middle, n - 1))
In [149]: list(partition_into_n(s, 3))
Out[149]:
[['', '', 'thisisateststring'],
['', 't', 'hisisateststring'],
['', 'th', 'isisateststring'],
['', 'thi', 'sisateststring'],
...
['thisisateststrin', '', 'g'],
['thisisateststrin', 'g', ''],
['thisisateststring', '', '']]
It's slower than the recursive solution for small n
,
def partitions_recursive(s, n):
if not n>1:
yield [s]
return
for i in range(len(s) + 1):
for tail in partitions_recursive(s[i:], n - 1):
yield [s[:i]] + tail
s = "thisisateststring"
In [150]: %timeit list(partition_into_n(s, 3))
1000 loops, best of 3: 354 µs per loop
In [151]: %timeit list(partitions_recursive(s, 3))
10000 loops, best of 3: 180 µs per loop
but as you might expect, it is faster for large n
(as the recursion depth increases):
In [152]: %timeit list(partition_into_n(s, 10))
1 loops, best of 3: 9.2 s per loop
In [153]: %timeit list(partitions_recursive(s, 10))
1 loops, best of 3: 10.2 s per loop