python - Comparing sublists and merging them -

i have list contains lot of sublists, pairs of numbers, looks like:

list = [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]] 

and want compare last digit of sublist first digit in next sublist , if match - merge them in 1 sublist. output 2 matching sublists that:

output = [[7, 8, 9]] 

and, of course, if there row of matching sublists merge them in 1 big sublist.

output = [[14, 15, 16, 17, 18, 19]] 

i thinking using itemgetter kind of key compare. like:

prev_digit = itemgetter(-1) next_digit = itemgetter(0) 

but realised don't understand how can use in python, due lack of knowledge. tried think of loop, didn't work out didn't know how implement "keys".

for kind of inspiration used python, comparison sublists , making list still have no solution.

also, list can kinda big (from human perspective, thousand pairs or stuff) i'm interested in efficient way this.

and yes, i'm new python, grateful explanation. of course can google, can avoid explaining functions in depth, general logic nice.

i think wrote once. can done single pass on list.

alist = [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]]  l = [alist[0][:]] e in alist[1:]:    if l[-1][-1] == e[0]:       l[-1].append(e[1])    else:       l.append(e[:]) 

the code reads start first pair. loop on rest. check if last element of last list same first element of pair. if append second element else append pair list.

this results in l being:

[[2, 3], [4, 5], [7, 8, 9], [11, 12], [14, 15, 16, 17, 18, 19], [20, 21]] 

if want largest sublist suggest:

>>> l = [[2, 3], [4, 5], [7, 8, 9], [11, 12], [14, 15, 16, 17, 18, 19], [20, 21]] >>> max(l, key=len) [14, 15, 16, 17, 18, 19] 

and evaluated:

>>> alist = [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]] >>>  >>> l = [alist[0][:]] >>> e in alist[1:]: ...    if l[-1][-1] == e[0]: ...       l[-1].append(e[1]) ...    else: ...       l.append(e[:]) ...  >>> l [[2, 3], [4, 5], [7, 8, 9], [11, 12], [14, 15, 16, 17, 18, 19], [20, 21]] >>> alist [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]] 

and compared. reduce solution takes 6.4 usecs:

$ python -mtimeit "list = [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]]" "reduce(lambda x,y: x[:-1] + [x[-1] + y[1:]] if x[-1][-1] == y[0] else x + [y], list[1:], [list[0]])" 100000 loops, best of 3: 6.4 usec per loop 

the loop takes 3.62 usecs:

$ python -mtimeit "alist = [[2, 3], [4, 5], [7, 8], [8, 9], [11, 12], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19], [20, 21]]" "l = [alist[0][:]]" "for e in alist[1:]:" "   if l[-1][-1] == e[0]:" "      l[-1].append(e[1])" "   else:" "      l.append(e[:])" 100000 loops, best of 3: 3.62 usec per loop 

on python 2.7.3. loop 56% faster. difference more pronounced larger inputs cost of list concatenation depends on sum of length of 2 lists. whereas appending list cheaper.