разложение строки на известные шаблоны - PullRequest
Новая
       13

разложение строки на известные шаблоны

2 голосов
/ 04 июля 2010

Вот список строк 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:

BBBBBBB

Здесь возможны разложения

BB BB BB BB BB

BBBB BBBB

BBBB BB BB

BB BB BBBB

BBB BBB BB

BB BBB BBB

Кто-нибудь может подсказать мне, как это сделать?Сейчас я не очень обеспокоен эффективностью.

1 Ответ

5 голосов
/ 04 июля 2010

Вот один из способов использования рекурсии: 

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
...