将一个字符串分成 n 个字符串后，返回所有可能的组合。

Question

我在stackoverflow上进行了搜索，但没有找到如何实现的方法。这可能涉及到itertools。

我想要找到把字符串分割成n个（长度相等或不相等都可以）子串的所有可能结果，例如将字符串“thisisateststring”分割成3个子串的情况。

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

- user3507230

---

允许空子字符串吗？ - Sven Marnach

那么从数学上讲，您正在寻找长度为“n”的字符串的所有不同可能的大小之和，然后对它们进行排列组合？ - C.B.

从他的问题中，我理解他只想知道将一个字符串分成n个子字符串的所有可能方法（所以当你连接s1 + s2 + s3时，你会得到原始字符串）。 - Paul

SvenMarnach，是的，它们是被允许的。 C.B.，是的，你可以这样说，但Paul的听起来更简洁，但可能与你所说的相同。 Paul，完全正确。 - user3507230

Answer 1

您可以在此处使用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]

输出：

['t', 'h', 'isisateststring']
['thisisateststri', 'n', 'g']

- YS-L

---

这不包括空字符串，而且扩展到空字符串很尴尬。 - Sven Marnach

Answer 2

在使用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和任何所需分区数k。

- Sven Marnach

---

我知道这是一个愚蠢（而且非常简单）的问题，但是否有一种方法可以返回一个列表，因为当我执行代码时，它返回：<generator object partitions at 0x1026230a0>。 - user3507230

调用方式为 list(partitions("abcde", 3))。 - Sven Marnach

Answer 3

这里是一份基于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

- unutbu