I got stuck coming up with an algorithm and I don't know what to do now.

I need to get from a to d but only by scrolling through these lists:

[e, d]
[a, b, c]
[d, a]
[a, b]
[a, e, b]

This is of course a simple example and the solution is:

[a → d]         // 3rd line
[a → e → d]     // 5th line   1st line
[a → b → e → d] // 2nd   5th   1st line

But I have to solve it in Python. I came up with two ways to solve this, the first was using for-loops, but the loops started repeating and got very time consuming, so I went with idea number 2. I was thinking of creating a list of all possible variants that start with a and end with d. And then check if this is possible in our specified lists.

from itertools import permutations
 
lst = ['a', 'b', 'c', 'd', 'e']

x = 'a'
y = 'd'

for i in range(1, len(lst)):
    perm = permutations(lst, i 1)

    for j in list(perm):
        if (j[0] == x) and (j[-1] == y):
            print(j)

But then somehow I got stuck and I don't know what to do now. Could someone please give me a hint? Or am I going about this all wrong?

edit:

I'm trying to find all the paths and print them.

CodePudding user response：

This is a graph problem where the lists are undirected edges between the nodes. For example:

[a, b, c]

means that there are undirected edges from a to b and c, from b to a and c, and from c to a and b. Of course, a -- b, also means b -- a. I have repeated the edges above only for clarity.

So, what you want to do is to create an adjacency list that represents all of these edges and apply backtracking since you want all the possible paths from source to target.

Here is some code that shows you the idea:

adj_list = collections.defaultdict(set)
for row in rows:
  for i, el in enumerate(row):
    for j in range(i 1, len(row):
        adj_list[el].add(row[j])
        adj_list[row[j]].add(el)

def backtrack(node, adj_list, seen, partial_res, res):
  if node == target:
    res.append(partial_res[:])
  
  for neighbor in adj_list[node]:
    if neighbor in seen: continue
    seen.add(neighbor)
    partial_res.append(neighbor)
    backtrack(neighbor, adj_list, seen, partial_res, res)
    partial_res.pop()
    seen.remove(neighbor)

res = []
backtrack(start, adj_list, set(), [], res)
print(res)

I haven't run this. But the code should give an idea of how backtracking works. It's a dfs where you check each possible path and keep track of the edges that you traveled. If it leads to destination, you save a copy of it in your final results.

Please note that this algorithm only visit each node once in each path.