Генерация путей для графа на основе строки 0 и 1 в Python - PullRequest
Новая
       17

Генерация путей для графа на основе строки 0 и 1 в Python

0 голосов
/ 25 октября 2018

У меня есть следующий график: график пяти состояний

Исходное состояние - «A».Если вход 0, он может перейти к «B» или «D», а если вход 1, он может перейти к «E».Я хочу все возможные пути для строки.Например, если в качестве входных данных используется строка «100», которую я хотел бы иметь в качестве последнего выхода:

'AEBD' 'AEDB'

Я создал функцию с двумя отдельными словарями, один дляПереходы «0» и другие для переходов «1».

Вот мой код: 

def possible_moves(play):
    posibles_one= {'A':['E'],
           'B':['A','C','E'],
           'C':['E'],
           'D':['A','E'],
           'E':['A','C']}
    posibles_zero= {'A':['B','D'],
           'B':['D'],
           'C':['B'],
           'D':['B'],
           'E':['B','D']}
    new_list = []
    state= 'A'
    for c in play:
        if c == '1':
            for k,v in posibles_one.items():
                if k == state:
                    new_list.extend([k,v])  
        state= new_list[-1][-1]     
        if c == '0':
            for k,v in posibles_zero.items(): 
                if k == state:
                    new_list.extend([k,v]) 
        state = new_list[-1][-1]      
    return new_list

Когда я запускаю свою функцию, я получаю следующий список: 

print(possible_moves('100'))
['A', ['E'], 'E', ['B', 'D'], 'D', ['B']]

Мой код частично работает.'A', ['E'] - это первый путь для входа 1.Тогда «E» может перейти к «B» или «D».От 'E' и с '0' вы можете пройти через ['B', 'D'].Но тогда у меня есть последний возможный путь для «D», а не для «B».Я не знаю, как перебирать элементы списка, который я генерирую.Есть идеи, как решить проблему?

...