将字符串分解为已知模式

Question

这里有一个包含字符串的Python列表：

patterns = [

"KBKKB",

"BBBK",

"BKB",

"KBBB",

"KBB",

"BKBB",

"BBKB",

"KKBKB",

"BKBK",

"KBKB",

"KBKBK",

"BBK",

"BB",

"BKKB",

"BBB",

"KBBK",

"BKKBK",

"KB",

"KBKBK",

"KKBKKB",

"KBK",

"BBKBK",

"BBBB",

"BK",

"KKBKBK",

"KBBKB",

"BBKKB",

"KKKKBB",

"KKB"

]

我有一个输入字符串，只包含字母K和B，长度可以随意。我想知道这个输入字符串所有可能的完整分解方式。举个例子，如果字符串是8个B：

BBBBBBBB

这里是可能的分解方式：

BB BB BB BB BB

BBBB BBBB

BBBB BB BB

BB BB BBBB

BBB BBB BB

BB BBB BBB

有没有人能指导我该怎么做？我现在不太关心效率问题。

Answer 1

这里有一种使用递归的方法：

def getPossibleDecompositions(s):
    if s == '':
        yield []
    else:
        for pattern in patterns:
            if s.startswith(pattern):
                for x in getPossibleDecompositions(s[len(pattern):]):
                    yield [pattern] + x

for x in getPossibleDecompositions('BBBBBBBB'):
    print x