将字符串拆分为n个字符串时返回所有可能的组合

Question

我为此搜索了stackoverflow，但找不到方法。它可能涉及到itertools。在

我想找到将一个字符串拆分成thisisateststring成n（长度相等或不等，不重要，两者都应包括在内）字符串的所有可能结果。在

例如，让n成为3：

[["thisisat", "eststrin", "g"], ["th", "isisates", "tstring"], ............]

Answer 1

使用itertools.combinations()在结果中包含空字符串将相当困难。编写自己的递归版本可能最简单：

def partitions(s, k):
    if not k:
        yield [s]
        return
    for i in range(len(s) + 1):
        for tail in partitions(s[i:], k - 1):
            yield [s[:i]] + tail

这将适用于任何字符串s的任意数量的所需分区。在

Answer 2

您可以在这里使用itertools.combinations。只需选择两个拆分点即可生成每个结果字符串：

from itertools import combinations
s = "thisisateststring"
pools = range(1, len(s))
res = [[s[:p], s[p:q], s[q:]] for p, q in combinations(pools, 2)]
print res[0]
print res[-1]

输出：

^{pr2}$

Answer 3

以下是根据code by 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))

---

^{pr2}$

---

它比小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