Retaining order while using Python's set difference

Question

I'm doing a set difference operation in Python:

x = [1, 5, 3, 4]
y = [3]

result = list(set(x) - set(y))
print(result)

I'm getting:

[1, 4, 5]

As you can see, the order of the list elements has changed. How can I retain the list x in original format?

Answer 1

It looks like you need an ordered set instead of a regular set.

>>> x = [1, 5, 3, 4]
>>> y = [3]
>>> print(list(OrderedSet(x) - OrderedSet(y)))
[1, 5, 4]

Python doesn't come with an ordered set, but it is easy to make one:

import collections

class OrderedSet(collections.Set):
    def __init__(self, iterable=()):
        self.d = collections.OrderedDict.fromkeys(iterable)

    def __len__(self):
        return len(self.d)

    def __contains__(self, element):
        return element in self.d

    def __iter__(self):
        return iter(self.d)

Hope this helps :-)

Answer 2

Sets are unordered, so you will need to put the results back in the correct order after doing your set difference. Fortunately you already have the elements in the order you want, so this is easy.

diff = set(x) - set(y)
result = [o for o in x if o in diff]

But this can be streamlined; you can do the difference as part of the list comprehension (though it is arguably slightly less clear that that's what you're doing).

sety = set(y)
result = [o for o in x if o not in sety]

You could even do it without creating the set from y, but the set will provide fast membership tests, which will save you significant time if either list is large.