Recursive function that finds all possible paths (of x steps) in a dictionary

Question

I have a dictionary which contains keys and values described as the following:

-each key is a tuple in which the first element is a color and the second element is a number, both as strings;

-each value is a list of one or more tuple, each one has the name of a color as first element and the name of a fruit as second element (again, both as strings).

Example:

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')]}

Then I have a list of numbers (as strings) which are exactly the numbers contained as the second element in the dictionary keys. Example:

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

What I want to do is to create a recursive function that, without importing libraries, takes as input a color (as string), a dictionary and a list of numbers as described above, and finds all possible paths which start at given input_color and list_of_w[0] and proceeds with the value corresponding to (input_color, list_of_w[iteration]) untill list_of_w[iteration] == len(list_of_w).

Since I’m not good at explaining (and I’m very sorry for that), I’ll give you an example of what I mean: Input:

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'

1st path:

('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')

2nd path:

('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')

3rd path:

('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')

At the end, the function should return a list of all the possible paths as tuples of (string_of_fruits, last_color), in this case:

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

First, I initialized some variables to help for some calculations:

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

Then I wrote the code of my function:

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)

Expected result should be:

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

Actual result of my function is:

('strawberry pineapple banana', 'White')

So it seems that my function has two problems:

1)it doesn't return a list, instead it returns a tuple;

2)it stops at the first path instead of searching for the other two.

Can someone help me to see what I'm doing wrong? It seems I'm having a lot of troubles trying to understand and use recursion properly.

As requested, this is my complete real code:

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)

Calling the function as:

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

should return:

('strawberry pineapple banana', 'White')

Answer 1

Ok, this is what I came up with:

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)

Output as requested

Answer 2

Simple to construct with a Recursive generator

Code

def r_find_path(given_dict, list_of_w, initial_color, path=None):
  ' Recursive generator'

  # Path holds the sequence of color, fruit 
  # tuples for a path
  if path is None:
    path = []
    
  # Base case
  # at end of path
  # since list_of_w is empty
  if not list_of_w:
    # Created desired string from path elements
    yield ' '.join(x[1] for x in path), path[-1][0]
    
  else:
    # key with this color and list_of_w value
    start = (initial_color, list_of_w[0])
    
    # Recursively list of values
    for end in given_dict[start]:
        yield from r_find_path(given_dict, list_of_w[1:], end[0], path + [end])
   

Test

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')]}
    
list_of_w = ['one', 'three', 'seven']
input_color = 'Red'
     
# Get list of all solutions     
result = list(r_find_path(given_dict, list_of_w, input_color))       
 # Display solution on each line
print(*result, sep = '\n')
       

Output

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