首先,编写一个函数来生成字符串的所有分区:
def partitions(s):
if s:
for i in range(1, len(s) + 1):
for p in partitions(s[i:]):
yield [s[:i]] + p
else:
yield []
这将迭代所有可能的第一个段(一个字符,两个字符等),并将这些段与字符串的相应剩余部分的所有分区组合在一起.
>>> list(partitions("4824"))
[['4', '8', '2', '4'], ['4', '8', '24'], ['4', '82', '4'], ['4', '824'], ['48', '2', '4'], ['48', '24'], ['482', '4'], ['4824']]
现在,您可以只过滤那些符合您条件的条件,即那些没有两个连续长度为1的子串的条件.
>>> [p for p in partitions("4824") if not any(len(x) == len(y) == 1 for x, y in zip(p, p[1:]))]
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]
这里,zip(p,p [1:])是迭代所有连续项对的常用方法.
更新:实际上,将约束直接合并到分区函数中也不是那么难.只需跟踪最后一段并相应地设置最小长度.
def partitions(s, minLength=1):
if len(s) >= minLength:
for i in range(minLength, len(s) + 1):
for p in partitions(s[i:], 1 if i > 1 else 2):
yield [s[:i]] + p
elif not s:
yield []
演示:
>>> print list(partitions("4824"))
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]