CODEWITHSUNDEEP
pythonlist
machineghost
machineghost

Reputation: 35770

Ordered intersection of two lists in Python

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?

Upvotes: 36

Views: 21234

Answers (2)

koffein
koffein

Reputation: 1882

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]

Upvotes: 15

Peter DeGlopper
Peter DeGlopper

Reputation: 37319

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.

Upvotes: 38

Related Questions