29

I know that in Python, if I have:

list_1 = [1,2,3]
list_2 = [2,3,4]

I can do the following to find the intersection between the two:

list(set(list_1) & set(list_2))
# = [2,3]

But there's one problem with that approach: sets don't maintain order the way that lists do. So if I actually have:

list_1 = [3,2,1]
list_2 = [2,3,4]

I get:

list(set(list_1) & set(list_2))
# = [2,3]

even though I'd prefer to have the order from the first list, ie.:

# = [3,2]

Is there an alternative intersection technique which keeps the resulting "intersection set" in the same order as the first list?

machineghost
  • 33,529
  • 30
  • 159
  • 234
  • 1
    related: [Python - Intersection of two lists](http://stackoverflow.com/q/642763/4279) e.g., [answer that uses list comprehension](http://stackoverflow.com/a/642992/4279) or [this comment that uses `filter`](http://stackoverflow.com/questions/642763/python-intersection-of-two-lists#comment459150_642895) -- both preserve order – jfs May 07 '14 at 21:53

2 Answers2

33
set_2 = frozenset(list_2)
intersection = [x for x in list_1 if x in set_2]

set instead of frozenset works too, I'm just increasingly in the habit of using immutable classes in cases where I don't intend to mutate the data. The point is that to maintain order you need to traverse the list in the order you want to maintain, but you don't want to have the n*m complexity of the naive approach: [x for x in list_1 if x in list_2]. Checking for membership in a set or similar hash-based type is roughly O(1), compared to O(n) for membership in a list.

Peter DeGlopper
  • 36,326
  • 7
  • 90
  • 83
  • The naive approach was good enough in my case (I've got lists of max length 10 or so); it worked great and was clearer to read. Thanks. – machineghost May 07 '14 at 21:48
12

Use the index-method of lists as sort criterion:

l1 = [3, 2, 1]
l2 = [2, 3, 4]
sorted(set(l1) & set(l2), key = l1.index)

Out:

[3, 2]
koffein
  • 1,792
  • 13
  • 21
  • 1
    This seems like a great solution too ... but I already implemented Peter's solution and it works, so I'm not going to mess with success :-) – machineghost May 07 '14 at 22:02
  • 4
    Bad idea. This solution will be O(n^2) as every element in the intersection has to search the list to find the index. Peter's solution is O(n). – Duncan Mar 17 '17 at 09:42
  • 1
    @Duncan Yes, almost true. In fact, it depends on the size of the intersection and the length of the list. But still, the answer provides an alternative to Peter's approach that can be useful in other cases, e.g. when the order is obtained by a third list. The complexity does not matter for small lists, hence, the answer is definitely useful and should not be downvoted... – koffein Apr 04 '17 at 02:03
  • 1
    If the order depends on a third list then you just use Peter DeGlopper's answer but replace `set_2` with a combination of the two lists. `set_2=set(l1) & set(l2)` then `intersection = [x for x in list_3 if x in set_2]` Still no need to do linear searches. – Duncan Apr 04 '17 at 08:30