decomposing a string into known patterns

Question

Here's the python list of strings:

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" ]

I have an input string that consist of K and B only of arbitrary length. I want to know all the possible complete decompositions of the input string. Just an example a string of 8 B:

BBBBBBBB

Here are possible decompositions

BB BB BB BB BB

BBBB BBBB

BBBB BB BB

BB BB BBBB

BBB BBB BB

BB BBB BBB

Can anyone guide me how to go about it? I am not much concerned about efficiency right now.

Answer 1

Here's one way using recursion:

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