python - 递归函数，在字典中查找(x步)所有可能的路径

Question

我有一个字典，其中包含如下所述的键和值:

-每个键都是一个元组，其中第一个元素是颜色，第二个元素是数字，均为字符串；

-每个值都是一个或多个元组的列表，每个元组都将颜色名称作为第一个元素，将水果名称作为第二个元素(同样，两者都是字符串)。

示例:

given_dict = {('Red', 'one'): [('Blue', 'strawberry'), ('Yellow', 'banana')], 
                ('Yellow', 'three'): [('Green', 'peach')], 
                ('Green', 'seven'): [('Purple', 'lemon')],
                ('Blue', 'three'): [('Purple', 'pineapple')],
                ('Purple', 'three'): [('Red', 'strawberry')], 
                ('Purple', 'seven'): [('White', 'banana'), ('Green', 'dragonfruit')], 
                ('White', 'seven') : [('Green', 'melon')]}

然后我有一个数字列表(作为字符串)，它们正是字典键中第二个元素包含的数字。 示例:

list_of_w = ['one', 'three', 'seven']

我想要做的是创建一个递归函数，无需导入库，将颜色(作为字符串)、字典和数字列表作为输入，如上所述，并找到所有可能的路径，从给定的 input_color 和 list_of_w[0] 开始，并以与 (input_color, list_of_w[iteration]) 对应的值继续，直到 list_of_w[iteration] == len(list_of_w)。

由于我不擅长解释(对此我感到非常抱歉)，我举个例子来说明我的意思: 输入:

given_dict = {('Red', 'one'): [('Blue', 'strawberry'), ('Yellow', 'banana')], 
                ('Yellow', 'three'): [('Green', 'peach')], 
                ('Green', 'seven'): [('Purple', 'lemon')],
                ('Blue', 'three'): [('Purple', 'pineapple')],
                ('Purple', 'three'): [('Red', 'strawberry')], 
                ('Purple', 'seven'): [('White', 'banana'), ('Green', 'dragonfruit')], 
                ('White', 'seven') : [('Green', 'melon')]}
list_of_w = ['one', 'three', 'seven']
input_color = 'Red'

第一条路径:

('Red', 'one') -> ('Blue', 'strawberry')       #input_color = 'Red' | list_of_w[0] = 'one'
('Blue', 'three') -> ('Purple', 'pineapple')   #input_color = 'Blue' | list_of_w[1] = 'three'
('Purple', 'seven') -> ('White', 'banana')     #input_color = 'Purple' | list_of_w[2] = 'seven'

1st path returns ('strawberry pineapple banana', 'White')

第二条路径:

('Red', 'one') -> ('Blue', 'strawberry')          #input_color = 'Red' | list_of_w[0] = 'one'
('Blue', 'three') -> ('Purple', 'pineapple')      #input_color = 'Blue' | list_of_w[1] = 'three'
('Purple', 'seven') -> ('Green', 'dragonfruit')   #input_color = 'Purple' | list_of_w[2] = 'seven'

2nd path returns ('strawberry pineapple dragonfruit', 'Green')

第三条路径:

('Red', 'one') -> ('Yellow', 'banana')           #input_color = 'Red' | list_of_w[0] = 'one'
('Yellow', 'three') -> ('Green', 'peach')        #input_color = 'Yellow' | list_of_w[1] = 'three'
('Green', 'seven') -> ('Purple', 'lemon')        #input_color = 'Green' | list_of_w[2] = 'seven'

3rd path returns ('banana peach lemon', 'Purple')

最后，该函数应返回所有可能路径的列表，作为 (string_of_fruits, last_color) 的元组，在本例中:

[('strawberry pineapple banana', 'White'), ('strawberry pineapple dragonfruit', 'Green'), (‘banana peach lemon', 'Purple')]

首先，我初始化了一些变量来帮助进行一些计算:

t = 0               #this will be increased by 1 each time: when (t == l) I may have found a path
l = len(list_of_w)  #to know when I finished the steps 
set_end = set()     #to save values I've already found before
list_of_fruits, result = list(), list()   #same as above

然后我编写了我的函数的代码:

def r_find_path(given_dict, t, l, result, list_of_fruits, list_of_w, initial_color, set_end):
    start = (initial_color, list_of_w[t])
    if (start not in given_dict.keys()):  
        return ()
    if (t == l): #arrived at the end
        for end in given_dict[start]:
            list_of_fruits.append(end[1])
            final_color = end[0]
            str_colors = ' '.join(list_of_fruits)
            set_end.add(end)
            result = [(str_colors, final_color)]
            t = 0
            list_of_fruits = list()
            return result[0] + r_find_path(given_dict, t, l, result, list_of_fruits, list_of_w, initial_color, set_end)
    else:   #if(t < l):
        for end in given_dict[start]:
            if (end not in set_end): 
                list_of_fruits.append(end[1])
                initial_color = end[0]
                set_end.add(end)
                return  r_find_path(given_dict, t+1, l, result, list_of_fruits, list_of_w, initial_color, set_end)

预期结果应该是:

[('strawberry pineapple banana', 'White'), ('strawberry pineapple dragonfruit', 'Green'), ('banana peach lemon', 'Purple')]

我的函数的实际结果是:

('strawberry pineapple banana', 'White')

看来我的函数有两个问题:

1)它不返回列表，而是返回元组；

2)它在第一条路径处停止，而不是搜索其他两条路径。

有人可以帮我看看我做错了什么吗？看来我在尝试正确理解和使用递归时遇到了很多麻烦。

根据要求，这是我完整的真实代码:

def  function(initial_color, string_of_w):
    given_dict = {('Red', 'one'): [('Blue', 'strawberry'), ('Yellow', 'banana')], 
                ('Yellow', 'three'): [('Green', 'peach')], 
                ('Green', 'seven'): [('Purple', 'lemon')],
                ('Blue', 'three'): [('Purple', 'pineapple')],
                ('Purple', 'three'): [('Red', 'strawberry')], 
                ('Purple', 'seven'): [('White', 'banana'), ('Green', 'dragonfruit')], 
                ('White', 'seven') : [('Green', 'melon')]}
    t = 0
    list_of_w = string_of_w.split()
    result, list_of_fruits = tuple(), list()
    l = len(list_of_w) - 1
    set_end = set()
    return r_find_path(given_dict, t, l, result, list_of_fruits, list_of_w, initial_color, set_end)
    
def r_find_path(given_dict, t, l, result, list_of_fruits, list_of_w, initial_color, set_end):
    start = (initial_color, list_of_w[t])
    if (start not in given_dict.keys()):  
        return ()
    if (t == l): #arrived at the end
        for end in given_dict[start]:
            list_of_fruits.append(end[1])
            final_color = end[0]
            str_colors = ' '.join(list_of_fruits)
            set_end.add(end)
            result = [(str_colors, final_color)]
            t = 0
            list_of_fruits = list()
            return result[0] + r_find_path(given_dict, t, l, result, list_of_fruits, list_of_w, initial_color, set_end)
    else:   #if(t < l):
        for end in given_dict[start]:
            if (end not in set_end): 
                list_of_fruits.append(end[1])
                initial_color = end[0]
                set_end.add(end)
                return  r_find_path(given_dict, t+1, l, result, list_of_fruits, list_of_w, initial_color, set_end)

调用函数为:

function('Red', 'one three seven')

应该返回:

('strawberry pineapple banana', 'White')

Answer 1

好的，这就是我的想法:

def search(given_dict, list_of_w, input_color, curr_str, ret):
    w = list_of_w[0]
    k = (input_color, w)
    nxt = given_dict[k]
    if len(list_of_w) == 1:
        for k in nxt:
            c, f = k
            final_str = curr_str[:] + [f]
            final_str = ' '.join(final_str)
            ret.append((final_str, c))
    else:
        for k in nxt:
            c, f = k
            nxt_str = curr_str[:] + [f]
            search(given_dict, list_of_w[1:], c, nxt_str, ret)


given_dict = {
    ('Red', 'one'): [('Blue', 'strawberry'), ('Yellow', 'banana')],
    ('Yellow', 'three'): [('Green', 'peach')],
    ('Green', 'seven'): [('Purple', 'lemon')],
    ('Blue', 'three'): [('Purple', 'pineapple')],
    ('Purple', 'three'): [('Red', 'strawberry')],
    ('Purple', 'seven'): [('White', 'banana'), ('Green', 'dragonfruit')],
    ('White', 'seven'): [('Green', 'melon')]
}
list_of_w = ['one', 'three', 'seven']
initial_color = 'Red'

ret = []
search(given_dict, list_of_w, initial_color, [], ret)
print(ret)

按要求输出