python - 获取任意长度的所有可能的 str 分区

Question

我想找到没有空字符串的字符串的所有可能分区，并且必须包含所有字符(不应包含原始字符串)

例如:

s = '1234'

partitions(s)  # -> [['1', '2', '3', '4'], ['1', '2', '34'], ['1', '23', '4']
               #     ['12', '3', '4'], ['12', '34'], ['1', '234'], ['123', '4']]
               # should not contain ['1234']

编辑:可以按任何顺序

为什么我的问题不是重复的:

我不想要这样的排列:

from itertools import permutations

s = '1234'
permutations(s) # returns ['1', '2', '3', '4'], ['1', '2', '4', '3']...

但是我想把字符串分成很多长度(请看第一段代码)

谢谢!

Answer 1

您可以定义递归(生成器)函数。其思想是:将所有长度的字符串的前缀与剩余字符串的所有分区组合起来。

def partitions(s):
    if len(s) > 0:
        for i in range(1, len(s)+1):
            first, rest = s[:i], s[i:]
            for p in partitions(rest):
                yield [first] + p
    else:
        yield []

partitions("1234") 的结果:

['1', '2', '3', '4']
['1', '2', '34']
['1', '23', '4']
['1', '234']
['12', '3', '4']
['12', '34']
['123', '4']
['1234']

请注意，这确实包含['1234']，但之后可以很容易地对其进行过滤，例如如 print([p for p in partitions("1234") if len(p) > 1])，或者您可以将结果收集到 list 中，然后 pop 最后一个元素。将其直接添加到递归函数中会更加复杂，因为除了顶级调用之外的每个调用都应该返回“完整”分区。