5

These are my two lists;

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]
kDash = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]

My output should be the following;

[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

how can I get to this output?

thank you in advance

Anshul Goyal
  • 73,278
  • 37
  • 149
  • 186
Nimmi Rashinika
  • 149
  • 1
  • 4
  • 14

4 Answers4

5

You will have to convert the lists to list of tuples, and then use the intersection. Note that below solution may have elements in a different order, and duplicates will obviously not be there, since I'm using set.

In [1]: l1 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]

In [2]: l2 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]

In [3]: [list(x) for x in set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))]
Out[3]: [[1, 2], [5, 6, 2], [3], [4]]

You can alternatively save the intersection in a variable and get the final list, if order, duplicates are necessary:

In [4]: intersection = set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))

In [5]: [x for x in l1 if tuple(x) in intersection]
Out[5]: [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

And the intersection, just in case if you are interested.

In [6]: print intersection
set([(1, 2), (5, 6, 2), (3,), (4,)])

This will work pretty well for large lists, but if the lists are small, do explore the other solution by @timegb (whose solution will be highly unoptimal for longer lists)

Anshul Goyal
  • 73,278
  • 37
  • 149
  • 186
3

Since your output list has duplicate elements, you don't really seem to want a classical intersection. A basic list comprehension will do everything.

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]
>>> kDash = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]
>>> [x for x in k if x in kDash]
[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

For large lists, we want to get the time it takes to call __contains__ to O(1) instead of O(n):

>>> stuff_in_kDash = set(map(tuple, kDash))
>>> [x for x in k if tuple(x) in stuff_in_kDash]
[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
timgeb
  • 76,762
  • 20
  • 123
  • 145
  • And if you need to remove the duplicate element, you can take a look at [this answer](http://stackoverflow.com/questions/2213923/python-removing-duplicates-from-a-list-of-lists) ;) – NiziL Jan 30 '16 at 11:23
  • 1
    This will be a *lot* slower than the `set` intersection methods. The scaling is something like `O(n²k)` where `n` is the number of sublists and `k` is the average length of each sublist. – Veedrac Jan 30 '16 at 11:24
  • I just realized that the OPs output list has duplicate elements. So the list comp is the way to go unless the specifications change. – timgeb Jan 30 '16 at 11:25
  • I think your optimized version may be recreating the `set` for testing on every loop, so it's not actually fixing the `O(n)` problem... – ShadowRanger Jan 30 '16 at 12:54
  • 1
    @ShadowRanger holy cow you are right, I just tested this with a subclass of `set` which prints something when `__init__` is called. I will edit my answer. – timgeb Jan 30 '16 at 12:57
2

A cleaner way to write the intersection is

{tuple(x) for x in l1} & {tuple(x) for x in l2}

A good alternative is

{tuple(x) for x in l1}.intersection(map(tuple, l2))
Veedrac
  • 58,273
  • 15
  • 112
  • 169
0

Even though what was written here is much more elegant solutions, here's another one

def foo(L1,L2):
    res=[]
    for lst in L1:
        if lst in L2:
            res.append(lst)
    return res
limitless
  • 669
  • 7
  • 18