分割字符串

Question

给定一个字符串，我想生成所有可能的组合。换句话说，就是在字符串中任意位置放置逗号的所有可能方式。

例如：

input:  ["abcd"]
output: ["abcd"]
        ["abc","d"]
        ["ab","cd"]
        ["ab","c","d"]
        ["a","bc","d"]
        ["a","b","cd"]
        ["a","bcd"]
        ["a","b","c","d"]

我有点困惑如何生成所有可能的列表。组合只会给我子字符串长度的列表，排列会给出所有可能的排序方式。

我可以通过遍历切片来生成仅包含一个逗号的列表，但对于包含两个逗号的情况，如 "ab"、"c"、"d" 和 "a"、"b"、"cd"，我无法生成。

我尝试使用切片：

test="abcd"

for x in range(len(test)):
     print test[:x],test[x:]

- Noob Coder

---

给itertools的评论者，是哪一页？我正在查看这个页面http://docs.python.org/2/library/itertools.html，但也许这不是正确的搜索页面。 - Noob Coder

在你给出的例子中漏掉了['a', 'bc', 'd']，因为在每个字母之间的位置，你可以选择拆分字符串或不拆分，因此总共有2^(n-1)种可能性。 - Karl Knechtel

Answer 1

怎么样，做个类似这样的东西：

from itertools import combinations

def all_splits(s):
    for numsplits in range(len(s)):
        for c in combinations(range(1,len(s)), numsplits):
            split = [s[i:j] for i,j in zip((0,)+c, c+(None,))]
            yield split

之后：

>>> for x in all_splits("abcd"):
...     print(x)
...     
['abcd']
['a', 'bcd']
['ab', 'cd']
['abc', 'd']
['a', 'b', 'cd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

- DSM

---

为什么不直接使用 yield，而不是将其存储在 split 中呢？ - thefourtheye

@thefourtheye：只是因为我倾向于逐行工作，当时我没有意识到我已经深入到需要使用yield的程度。: ^) 当然，你是对的，没有必要将本地变量绑定到它上面。 - DSM

这一行代码让我感到非常惊奇：split = [s[i:j] for i,j in zip((0,)+c, c+(None,))]，但是我终于搞懂了！ - Noob Coder

@NoobCoder：是的，这个习惯用语对于获取一堆分割位置并生成相应序列非常有用。 - DSM

Answer 2

你当然可以使用 itertools 来实现这个，但我认为直接编写一个递归生成器会更容易：

def gen_commas(s):
    yield s
    for prefix_len in range(1, len(s)):
        prefix = s[:prefix_len]
        for tail in gen_commas(s[prefix_len:]):
            yield prefix + "," + tail

那么

print list(gen_commas("abcd"))

打印

['abcd', 'a,bcd', 'a,b,cd', 'a,b,c,d', 'a,bc,d', 'ab,cd', 'ab,c,d', 'abc,d']

我不确定为什么我觉得这样更容易。也许只是因为这样直接做起来非常容易 ;-)

- Tim Peters

---

现在尝试一下在一个非常长的字符串上这样做。（我知道，我知道，不要牵扯超人的斗篷。。） - DSM

Answer 3

使用itertools：

import itertools
input_str =  "abcd"
for k in range(1,len(input_str)):
    for subset in itertools.combinations(range(1,len(input_str)), k): 
        s = list(input_str)
        for i,x in enumerate(subset): s.insert(x+i, ",")
        print "".join(s)

给出：

a,bcd
ab,cd
abc,d
a,b,cd
a,bc,d
ab,c,d
a,b,c,d

另外还有一种递归版本：

def commatoze(s,p=1):
    if p == len(s):
        print s
        return
    commatoze(s[:p] + ',' + s[p:], p + 2)
    commatoze(s, p + 1)

input_str =  "abcd"
commatoze(input_str)

- perreal

---

在回答之前的问题时，有更多生成幂集的选项：https://dev59.com/m3M_5IYBdhLWcg3wMgEF - James King

Answer 4

你可以生成n-1个位置的幂集，这些位置都可以放置逗号：
如何组合一个集合？
然后在每个位置插入逗号。

- James King

Answer 5

您可以解决整数拆分问题并使用拆分结果来指导如何分割列表。只需一点动态规划就可以相对容易地解决整数拆分问题。

def composition(n):
    if n == 1: 
        return [[1]] 
    comp = composition (n - 1) 
    return [x + [1] for x in comp] + [y[:-1] + [y[-1]+1] for y in comp]

def split(lst, guide):
    ret = []
    total = 0
    for g in guide:
        ret.append(lst[total:total+g])
        total += g
    return ret

lst = list('abcd')
for guide in composition(len(lst)):
    print split(lst, guide)

另一种生成整数组合的方法：

from itertools import groupby
def composition(n):
    for i in xrange(2**(n-1)):
        yield [len(list(group)) for _, group in groupby('{0:0{1}b}'.format(i, n))]

- Lie Ryan

Answer 6

给定

import more_itertools as mit

代码

list(mit.partitions("abcd"))

输出

[[['a', 'b', 'c', 'd']],
 [['a'], ['b', 'c', 'd']],
 [['a', 'b'], ['c', 'd']],
 [['a', 'b', 'c'], ['d']],
 [['a'], ['b'], ['c', 'd']],
 [['a'], ['b', 'c'], ['d']],
 [['a', 'b'], ['c'], ['d']],
 [['a'], ['b'], ['c'], ['d']]]

通过> pip install more-itertools安装more_itertools。

- pylang