首先,編寫一個函數來生成字元串的所有分區:
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']]