1

I am developing a program in python and as part of it I have to link all the lists that have an element in common in a certain position, that is, there is an input element and an output element and I want to gather all those that follow the chain. For example, we have as input a list :

list_array = [[n_element, l_input, l_ouput], .....]

A concrete example would be

list_array = [[1,a,b],[2,c,d],[3,e,f],[4,b,e],[5,d,f],[6,a,e],[7,b,c]

The result of the program should be a list where the elements are linked by input and output.

res_array = [[1,4,3],[1,7,2,5],[6,3]]

The result of the program should be a list where the elements are linked by input and output. If there is one element included in another, the element with greater length prevails. My first thought was to use a tree structure, a search in depth or length. I need ideas.

dimitruss
  • 11
  • 3
  • Are they always perfect chains or can there be overlap? For example can multiple elements with different inputs map to the same output? – CMMCD Nov 18 '19 at 19:24
  • yes they can overlaf, this answer is valid ex: [ [1,4,5],[1,4,8] ] – dimitruss Nov 18 '19 at 21:11

1 Answers1

0

You could use a graph representation of this problem:

For each element [n_element, l_input, l_output], you add vertices l_input and l_output to your graph (if not already present) and add an edge labelled n_element (from l_output to l_input).

Then, you look for paths through that graph. The resulting list is then given by the concatenation of edge labels.

phimuemue
  • 34,669
  • 9
  • 84
  • 115
  • You know the algoritm to do this? BFS? DFS? , I have the structure and it is a directed graph with cycles. – dimitruss Nov 24 '19 at 01:46
  • Enumerating all paths in a graph: https://stackoverflow.com/questions/20262712/enumerating-all-paths-in-a-directed-acyclic-graph, but you can possibly be more clever than simply enumerating all and filtering them. – phimuemue Nov 24 '19 at 17:53