这里是一份基于Raymond Hettinger的代码将一个序列分成n组的配方:
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', '', '']]
对于小的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
但是正如你所预料的那样,对于大的n
(随着递归深度的增加),它会更快:
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