Find patterns in python lists

Navigation
2

I have a somewhat complex problem, on the one hand I have a list that contains lists. These contain integers that represent positions on a map: 

rutas = [[0,1,2,3],[0,1,2],[7,4,8],...[5,6],[0,1,3,4]]

I also have another list, which contains, according to its position in the list, the coordinates of each of these integers and a third value that says if it is an entry, exit or intermediate point. 

mu = [[12,13,'ent'],[15,-3,'sal'],...[67,0,'med']]

Therefore mu[0] , corresponds to the integer 0 in rutas .

What I try to do but I can not find is to find in rutas , sequences of numbers that go from an 'ent' to a 'salt' and be able to plot them. I explain myself better with an example.

Suppose that the point 0 es 'ent' and that 4 y 3 son 'sal' , among others ... I want to be able to find in routes, those sequences that go from 0 to 4 and from 0 to 3, regardless of whether 0 is the first value in routes and 4 or 3 the last. That is, even being in the middle of the list. And also if I have a route that is: [0,1,2,3] and another that is [0,1,2] that the latter account as if it belonged to [0,1,2,3] .

The idea is then once I have selected all the paths that go from ent -> sal to plot the corresponding mu coordinates.

If at least you know how to approach it or if there is a function that can help.

    
asked by Juanca M 18.07.2017 в 07:39
source

1 answer

1

Without being well defined as a problem, I intuit that what you are trying to do is draw a graph without drawing twice the same connection. That a path does not pass through the same edge twice is what is known by "eugeniano path" and you can find a lot of bibliography on how to deal with this type of problem, although do not be surprised if you do not find a definitive solution.

Before answering your problem, there are some doubts and assumptions:

  • Are all routes well defined? I suppose so and that all routes start at node ent and end at one sal . (Otherwise, the first thing would be to purge the list of routes).
  • You say that the nodes ent and sal can be in the middle, that is, they can make med . Is it possible for a node ent to appear elsewhere as sal or vice versa? Is it possible that there are cycles, that is, a route that starts and ends at the same point? I'm going to assume that there are no closures , that a dot ent always appears as ent and one sal always as sal .
  • What about overlaps ? Is there transitivity ? Suppose we have two routes, [0,1,2] and [1,2,3] , 0 and 1 are ent , and 2 and 3 are sal . Should we take them as two independent routes or would they form a single path [0,1,2,3] ? For simplicity, I will consider that there is no overlap , that is, a route is discarded only if it is contained in another.

    • With these assumptions it is enough to verify that one route is not included in another: 

    def is_included(ruta, rutas):
    n = len(ruta)
    subrutas = (r[i:i+n] for r in rutas for i in range(len(r)-n+1))
    return ruta in subrutas

sel = [ruta for (i,ruta) in enumerate(sorted(rutas, key=len))
      if not is_included(ruta, rutas[i+1:])]

    If the list of routes is very large, it is necessary to use some strategy that decreases the number of comparisons ....

        
    answered by 18.07.2017 в 17:53
    Android Should I use a doInBackground inside an AlertDialog? Import a UI schema in PySide