Find patterns in python lists

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 в 09:39
source

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.

• 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 ....