Finding common elements from two lists of lists

Question

I have two lists of lists containing some 3D coordinates like this (for example):

a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]
b[n] = [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]

What will be a fast way of finding if any of the elements of "b" have any coordinate in the list "a"? For example, in the given example "a[2]" and "b[2][1]" are the same and so I want the program to return "true".

Did you mean `a[1]` and `b[2][1]` in your question? – TerryA Jun 14 '13 at 08:04 — TerryA, Jun 14 '13 at 08:04
yes, sorry! I will edit it. – Pradeep Kumar Jha Jun 14 '13 at 08:09 — Pradeep Kumar Jha, Jun 14 '13 at 08:09

Ashwini Chaudhary · Accepted Answer · 2013-06-14T08:18:16.590

4

Convert the innermost lists of b into a set(s), and then iterate over a to check whether any item in a exist in s or not.

tot_items_b = sum(1 for x in b for y in x) #total items in b

Sets provide an O(1) lookup, so the overall complexity is going to be :

O(max(len(a), tot_items_b))

def func(a, b):
   #sets can't contain mutable items, so convert lists to tuple while storing

   s = set(tuple(y) for x in b for y in x)
   #s is set([(41, 2, 34), (98, 23, 56), (42, 25, 64),...])

   return any(tuple(item) in s for item in a)

Demo:

>>> a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
>>> b = [[[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]], [[11, 22, 3], [42, 25, 64], [43, 45, 23]], [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]]
>>> func(a,b)
True

Help on any:

>>> print any.__doc__
any(iterable) -> bool

Return True if bool(x) is True for any x in the iterable.
If the iterable is empty, return False.

Use set intersection to get all the common elements:

>>> s_b = set(tuple(y) for x in b for y in x)
>>> s_a = set(tuple(x) for x in a)
>>> s_a & s_b
set([(4, 5, 6)])

edited Jun 14 '13 at 08:18

answered Jun 14 '13 at 07:59

Ashwini Chaudhary

244,495
58
464
504

is it possible to edit this program to output the common element? thank you! – Pradeep Kumar Jha Jun 14 '13 at 08:09
@jhaprade first common element or all of them? – Ashwini Chaudhary Jun 14 '13 at 08:09
I believe the complexity is `O(max(len(a), sum_{i=0}^{len(b)-1}{len(b[i])}))` since when creating the `set` you are doing a nested loop. – Bakuriu Jun 14 '13 at 08:11
@Ashwini I would like to have all of them if possible. – Pradeep Kumar Jha Jun 14 '13 at 08:11
@Bakuriu Whoops! good point. But I didn't understand the notation you're using? – Ashwini Chaudhary Jun 14 '13 at 08:16
@AshwiniChaudhary It should be a LaTeX-like formula(sum over the indices of b of the length of b elements i.e. total number of elements inside b). – Bakuriu Jun 14 '13 at 09:07
`sum(1 for x in b for y in x)` can be `sum(len(x) for x in b)` – jamylak Jun 14 '13 at 12:39

TerryA · Answer 2 · 2013-06-14T08:09:26.290

3

Use itertools.chain.from_iterable to flatten the list first, then simply iterate through it:

>>> B = [[[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]], [[11, 22, 3], [42, 25, 64], [43, 45, 23]], [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]], [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]]
>>> A = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
>>> for i in itertools.chain.from_iterable(B):
...     if i in A:
...             print True, i
... 
True [4, 5, 6]

edited Jun 14 '13 at 08:09

answered Jun 14 '13 at 08:03

TerryA

58,805
11
114
143

1

@Jared Fast way to flatten the list – TerryA Jun 14 '13 at 08:12

perreal · Answer 3 · 2013-06-14T13:45:38.363

Using numpy:

import numpy
b=[ [], [] , [] ]
a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], 
        [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]

for p1 in a:
    for p2 in [ p for bb in b for p in bb]:
        v=numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))
        if v == 0: print p1

score 0 · Answer 4 · edited Jun 14 '13 at 08:18

0

try this code:

a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b={}
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]
b[3] = [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]

for i in b:
    for ii in i:
        if ii in a:
            return True

It works but I don't sure it's fast or not.

edited Jun 14 '13 at 08:18

lvc

34,233
10
73
98

answered Jun 14 '13 at 08:10

htynkn

104
5

1

It would be faster with `any` and a generator - `any(ii in a for i in b for ii in i)`, but it probably still won't compete with the answer using sets (except possibly for very small input sizes). It *might* compete with the `itertools.chain` solution, but will probably still be a bit slower. – lvc Jun 14 '13 at 08:17
@lvc Compete? Hey now, this isn't a competition. I'm just supplying my answer because it's another way to answer the question. – TerryA Jun 14 '13 at 08:19
2

You should initialise `b` as a list: `b = []`, not dict. otherwise in the loop `for ii in i:` you're actually trying to iterate over an integer. – Ashwini Chaudhary Jun 14 '13 at 08:20

Finding common elements from two lists of lists

4 Answers4

Linked