How to make a dict point to and get to "follow" and get all possible combinations of path (I kind of wanted to know the logic behind it) Example :

{1: [3, 8, 15], 2: [7, 14], 3: [1, 6, 13], 4: [5, 12], 5: [4, 11], 6: [3, 10], 7: [2, 9], 8: [1], 9: [7], 10: [6, 15], 11: [5, 14], 12: [4, 13], 13: [3, 12], 14: [2, 11], 15: [1, 10]}

here 1 points to 3, 8, 15 (path terminates if it reaches a checkpoint it has reached before) so the path looks like :

1 - > 3
1 - > 8 # End
1 -> 15

3, 8, 15 points to (6, 13), (), (10) respectively making it

1 -> 3 -> 6
1 -> 3 -> 13
1 -> 15 -> 10

This leads to :

1 -> 3 -> 6 -> 10
1 -> 3 -> 13 -> 12
1 -> 15 -> 10 -> 6

How to do this but automatically, maybe like a function which takes a dict and returns all the path combinations like this?

CodePudding user response：

Here is one approach using a recursive function.

In summary, keep a list of seen elements and walk down the path (here also keeping a set for efficiency). Only check never seen elements. If there are no children to test, we are at the end of the path.

def get_child(val, seen=set(), path=[]):
    seen.add(val)
    path.append(val)
    to_check = set(d[val]).difference(seen)
    if not to_check:
        print(path)
    for e in to_check:
        get_child(e, seen.copy(), path.copy())

get_child(1)

Output:

[1, 8]
[1, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]
[1, 3, 6, 10, 15]
[1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9]

using a generator instead of print

def get_child(val, seen=set(), path=[]):
    seen.add(val)
    path.append(val)
    to_check = set(d[val]).difference(seen)
    if not to_check:
        yield path
    for e in to_check:
        yield from get_child(e, seen.copy(), path.copy())
    
list(get_child(1))

Output:

[[1, 8],
 [1, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9],
 [1, 3, 6, 10, 15],
 [1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9],
]