Python recursive function to generate a specific type of sequence from a specific type of dictionary

Question

I need to write an algorithm where I have a python dictionary like {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]} and generate the sequence like [[1, 2, 3, 4, 5,8],[1, 2, 3, 4, 5,9], [1,2,3,4,7], [1, 6, 5,8], [1, 6, 5,9]].

Here basically it would start with the first elements of the dictionary and append the values to the key. It should create n number of list where n is the size of the list of values. for eg. in first loop 2 lists are created [1,2] and [1,6], further it should check if the last value of any of the list is the key value, it should append its value to that particular list. Here since 2 is the last value of first list it will append [1,2,3] and the lists are [1,2,3] and [1,6]. Further in next iteration of dict, the lists are updated to [1,2,3] and [1,6, 5] and so on. Hope you got the point and finally it should end up with the above list of lists.

My solution: lists = [] lines = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [], 4: [5,7]}

def create_lines(cont=False):
    for k,val in lines.items():
        print(lists)
        for l in lists:
            if k==l[-1]:
                if lines[k]:
                    l.append(lines[k][0])
                    cont=True
                    break
        if cont:               
            continue

        for v in val:
            lists.append(list([k,v]))
            cont=False
    for l in lists:
        print("second loop")
        if l[-1] in lines and lines[l[-1]]:
            create_lines()
    
create_lines()

goes to infinite loop

From chatGPT:

def all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.get(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            new_paths = all_paths(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths

# Given dictionary
graph_dict = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}

# Define the start and end points
start_point = 1
end_point = 8

# Find all possible paths
paths = all_paths(graph_dict, start_point, end_point)

# Filter paths that do not end with the end point
valid_paths = [p for p in paths if p[-1] == end_point]

# Print the valid paths
print(valid_paths)

and result: [[1, 2, 3, 4, 5, 8], [1, 6, 5, 8]]

Answer 1

Try:

dct = {1: [2, 6], 2: [3], 6: [5], 3: [4], 5: [8, 9], 4: [5, 7]}


def get_lists(d, start):
    if start[-1] not in d:
        yield start
        return

    for v in d[start[-1]]:
        yield from get_lists(d, start + [v])


print(list(get_lists(dct, [1])))

Prints:

[
 [1, 2, 3, 4, 5, 8], 
 [1, 2, 3, 4, 5, 9], 
 [1, 2, 3, 4, 7], 
 [1, 6, 5, 8], 
 [1, 6, 5, 9]
]