I have a route of a car but how can i make it simple(by using list)

Question

I have a list like:

A=[(0, 16), (1, 11), (2, 4), (3, 14), (4, 8), (5, 15), (6, 13), (7, 2), (8, 20), (9, 17), (10, 5), (11, 12), (12, 6), (13, 7), (14, 0), (15, 1), (16, 19), (17, 18), (18, 10), (19, 9), (20, 3)]

This is a route of a car.For example this car leaves from 0 to 16(0,16) then it goes from 16 to 19(16,19) than it goes from 19 to 9 etc. For big datasets it is hard to follow this route. I try to write loops but couldn't succeed.I have to convert this A list to another list like

B=[0,16,19,9,17,18,10,5,15,1,11,12,6,13,7,2,4,8,20,3,14,0]

Is each first and second element an combination to of routes? Like 0 to 16, 19 to 9, 17 to 18? — 3dSpatialUser, Jan 14 '22 at 08:41
Does it always start at 0 or does it always start at the first tuple in the list? As in if the first tuple in the list was (12, 16), would B start at 12? — spo, Jan 14 '22 at 08:42
Its a route of car.And every number is an address.So it begins route with 0 than goes to 16 than goes 19....... — özgür Sanli, Jan 14 '22 at 08:59

hiro protagonist · Accepted Answer · 2022-01-14T08:59:14.083

if you convert your list A to a dictionary the lookups are much faster:

A_dict = dict(A)

start = 0
route = [start]
frm = start
while True:
    to = A_dict[frm]
    route.append(to)
    frm = to
    if to == start:
        break
print(route)

for your given A you get the route

[0, 16, 19, 9, 17, 18, 10, 5, 15, 1, 11, 12, 6, 13, 7, 2, 4, 8, 20, 3, 14, 0]

the edges of your graph are stored in A_dict as

{0: 16, 1: 11, 2: 4, 3: 14, 4: 8, 5: 15, 6: 13, 7: 2, 8: 20, 9: 17, 10: 5, ...}

if you perform the lookup for the next hop in your list A the overall performance of your approach will be quadratic (in the length of the list A). the approach with the dictionary grows linearly in the length of A.

a slightly shorter version:

start = 0
route = [start]
while True:
    route.append(to := A_dict[route[-1]])
    if to == start:
        break

dang, I spent some minutes on this and but looks like you had the same solution 13 mins earlier. +1 — , Jan 14 '22 at 08:58

score 1 · Answer 2 · answered Jan 14 '22 at 08:40

1

It looks like you want to flatten the list (Transform "list of tuples" into a flat list or a matrix):

flattened = [item for sublist in l for item in sublist]

answered Jan 14 '22 at 08:40

DSteman

1,388
2
12
25

that is not what the OP wants. their desired result is not `[0, 16, 1, 11, ...]` which is the result you'd get by flattening the list. – hiro protagonist Jan 14 '22 at 08:55
Must have misinterpreted the desired result `B` in the question – DSteman Jan 14 '22 at 09:42

score 1 · Answer 3 · answered Jan 14 '22 at 08:55

You can arrive at your desired list in two steps:

(i) Convert A to a dictionary. That way we can traverse A like the car

dict_A = dict(A)

(ii) Now traverse dict_A where every time you reach a tuple, you add the first element to out and go to the next destination according to dict_A. You do this until you come back to the start of out.

out = [A[0][0]]
while True:
    out.append(dict_A[out[-1]])
    if out[-1] == out[0]:
        break

Output:

[0, 16, 19, 9, 17, 18, 10, 5, 15, 1, 11, 12, 6, 13, 7, 2, 4, 8, 20, 3, 14, 0]

score 0 · Answer 4 · answered Jan 17 '22 at 07:15

Here is a recursive implementation if that helps.

# convert routes to dict
route_dict = dict(A)
# create empty list for storing results
route_dict_updated = []

def traverse(node, visited=[]):
    # return if node is already visited
    if node in visited:
        return
    route_dict_updated.append(route_dict[node])
    # add node to visited
    visited.append(node)
    # recurse
    traverse(route_dict[node], visited=visited)

start = 0
route_dict_updated.append(start)
traverse(start)
print(route_dict_updated)

I have a route of a car but how can i make it simple(by using list)

4 Answers4