Ordered intersection of two lists in Python

Question

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?

Answer 1

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.

Answer 2

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]