Find intersection of two nested lists

Question

I know how to get an intersection of two flat lists  b1    1 2 3 4 5 9 11 15  b2    4 5 6 7 8  b3    val for val in b1 if val in b2   or def intersect a  b       return list set a   amp  set b     print intersect b1  b2   But when I have to find intersection for nested lists then my problems starts  c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16    In the end I would like to receive  c3     13 32   7 13 28   1 6    Can you guys give me a hand with this  Related  Flattening a shallow list in python

User · Accepted Answer

If you want   c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16   c3     13  32    7  13  28    1 6     Then here is your solution for Python 2   c3    filter lambda x  x in c1  sublist  for sublist in c2    In Python 3 filter returns an iterable instead of list  so you need to wrap filter calls with list     c3    list filter lambda x  x in c1  sublist   for sublist in c2    Explanation    The filter part takes each sublist s item and checks to see if it is in the source list c1   The list comprehension is executed for each sublist in c2

User · Answer

I don t know if I am late in answering your question  After reading your question I came up with a function intersect   that can work on both list and nested list  I used recursion to define this function  it is very intuitive  Hope it is what you are looking for   def intersect a  b       result        for i in b          if isinstance i list               result append intersect a i           else              if i in a                   result append i      return result   Example    gt  gt  gt  c1    1  6  7  10  13  28  32  41  58  63   gt  gt  gt  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16    gt  gt  gt  print intersect c1 c2    13  32    7  13  28    1  6     gt  gt  gt  b1    1 2 3 4 5 9 11 15   gt  gt  gt  b2    4 5 6 7 8   gt  gt  gt  print intersect b1 b2   4  5

User · Answer

The functional approach   input list     1  2  3  4  5    2  3  4  5  6    3  4  5  6  7    result   reduce set intersection  map set  input list     and it can be applied to the more general case of 1  lists

User · Answer

Given    gt  c1    1  6  7  10  13  28  32  41  58  63    gt  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16     I find the following code works well and maybe more concise if using set operation    gt  c3    list set f  amp set c1   for f in c2     It got    gt    32  13    28  13  7    1  6     If order needed    gt  c3    sorted list set f  amp set c1    for f in c2     we got    gt    13  32    7  13  28    1  6     By the way  for a more python style  this one is fine too    gt  c3      i for i in set f  if i in c1  for f in c2

User · Answer

You don t need to define intersection   It s already a first-class part of set    gt  gt  gt  b1    1 2 3 4 5 9 11 15   gt  gt  gt  b2    4 5 6 7 8   gt  gt  gt  set b1  intersection b2  set  4  5

User · Answer

c1    1  6  7  10  13  28  32  41  58  63   c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16    c3    list set c2 i   intersection set c1    for i in xrange len c2     c3 - gt   32  13    28  13  7    1  6

User · Answer

Pure list comprehension version   gt  gt  gt  c1    1  6  7  10  13  28  32  41  58  63   gt  gt  gt  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16    gt  gt  gt  c1set   frozenset c1    Flatten variant    gt  gt  gt   n for lst in c2 for n in lst if n in c1set   13  32  7  13  28  1  6    Nested variant    gt  gt  gt    n for n in lst if n in c1set  for lst in c2    13  32    7  13  28    1  6

User · Answer

Problem   Given c1 and c2  c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16     how do you get c3 to be   13  32    7  13  28    1  6       Here s one way to set c3 that doesn t involve sets   c3      for sublist in c2      c3 append  val for val in c1 if val in sublist     But if you prefer to use just one line  you can do this   c3     val for val in c1 if val in sublist   for sublist in c2    It s a list comprehension inside a list comprehension  which is a little unusual  but I think you shouldn t have too much trouble following it

User · Answer

For people just looking to find the intersection of two lists  the Asker provided two methods    b1    1 2 3 4 5 9 11 15  b2    4 5 6 7 8  b3    val for val in b1 if val in b2        and  def intersect a  b        return list set a   amp  set b    print intersect b1  b2     But there is a hybrid method that is more efficient  because you only have to do one conversion between list set  as opposed to three   b1    1 2 3 4 5  b2    3 4 5 6  s2   set b2  b3    val for val in b1 if val in s2    This will run in O n   whereas his original method involving list comprehension will run in O n 2

User · Answer

c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16   c3    list set i   amp  set c1   for i in c2  c3   32  13    28  13  7    1  6     For me this is very elegant and quick way to to it

User · Answer

Since intersect was defined  a basic list comprehension is enough    gt  gt  gt  c3    intersect c1  i  for i in c2   gt  gt  gt  c3   32  13    28  13  7    1  6     Improvement thanks to S  Lott s remark and TM  s associated remark    gt  gt  gt  c3    list set c1  intersection i   for i in c2   gt  gt  gt  c3   32  13    28  13  7    1  6

User · Answer

The  amp  operator takes the intersection of two sets    1  2  3   amp   2  3  4  Out 1    2  3

User · Answer

Do you consider  1 2  to intersect with  1   2    That is  is it only the numbers you care about  or the list structure as well   If only the numbers  investigate how to  flatten  the lists  then use the set   method

User · Answer

A pythonic way of taking the intersection of 2 lists is    x for x in list1 if x in list2

User · Answer

To define intersection that correctly takes into account the cardinality of the elements use Counter   from collections import Counter   gt  gt  gt  c1    1  2  2  3  4  4  4   gt  gt  gt  c2    1  2  4  4  4  4  5   gt  gt  gt  list  Counter c1   amp  Counter c2   elements     1  2  4  4  4

User · Answer

I was also looking for a way to do it  and eventually it ended up like this   def compareLists a b       removed    x for x in a if x not in b      added    x for x in b if x not in a      overlap    x for x in a if x in b      return  removed added overlap

User · Answer

Simple way to find difference and intersection between iterables  Use this method if repetition matters  from collections import Counter  def intersection a  b               Find the intersection of two iterables       gt  gt  gt  intersection  1 2 3    2 3 4        2  3        gt  gt  gt  intersection  1 2 3 3    2 3 3 4        2  3  3        gt  gt  gt  intersection  1 2 3 3    2 3 4 4        2  3        gt  gt  gt  intersection  1 2 3 3    2 3 4 4        2  3              return tuple n for n  count in  Counter a   amp  Counter b   items   for   in range count    def difference a  b               Find the symmetric difference of two iterables       gt  gt  gt  difference  1 2 3    2 3 4        1  4        gt  gt  gt  difference  1 2 3 3    2 3 4        1  3  4        gt  gt  gt  difference  1 2 3 3    2 3 4 4        1  3  4  4              diff   lambda x  y  tuple n for n  count in  Counter x  - Counter y   items   for   in range count       return diff a  b    diff b  a

User · Answer

flat list can be made through reduce easily   All you need to use initializer - third argument in the reduce function   reduce     lambda result   list  result append         list set  list  amp set c1           or result      c2            Above code works for both python2 and python3  but you need to import reduce module as from functools import reduce  Refer below link for details    for python2 for python3

User · Answer

We can use set methods for this   c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16       result          for li in c2         res   set li   amp  set c1         result append list res       print result

User · Answer

You should flatten using this code   taken from http   kogs-www informatik uni-hamburg de  meine python tricks    the code is untested  but I m pretty sure it works    def flatten x          flatten sequence  -  list      Returns a single  flat list which contains all elements retrieved     from the sequence and all recursively contained sub-sequences      iterables        Examples           1  2   3 4    5 6        1  2   3  4    5  6           flatten    1 2 3    42 None     4 5    6   7  MyVector 8 9 10         1  2  3  42  None  4  5  6  7  8  9  10          result          for el in x           if isinstance el   list  tuple            if hasattr el     iter     and not isinstance el  basestring               result extend flatten el           else              result append el      return result   After you had flattened the list  you perform the intersection in the usual way    c1    1  6  7  10  13  28  32  41  58  63  c2     13  17  18  21  32    7  11  13  14  28    1  5  6  8  15  16    def intersect a  b        return list set a    set b    print intersect flatten c1   flatten c2

[python] Find intersection of two nested lists?

Examples related to python

Examples related to list

Examples related to intersection