How can I get the difference between two lists?

Question

>>> x1=[["x1","y1"],["x1","x2"]]  
>>> x2=[["x1","y1"],["x1","x2"],["x2","y2"]]  
>>> x2-x1  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for -: 'list' and 'list'
>>> set(x2)-set(x1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

I want to get the difference between two lists, the result I want here is ["x2","y2"]. How can I get it?

sshashank124 · Answer 1 · 2014-07-06T13:54:07.717

3

You can do it as follows by checking element-wise:

x1=[["x1","y1"],["x1","x2"]]  

x2=[["x1","y1"],["x1","x2"],["x2","y2"]]

>>> print [i for i in x2 if i not in x1]
[['x2', 'y2']]

edited Jul 06 '14 at 13:54

answered Jul 06 '14 at 13:15

sshashank124

31,495
9
67
76

@lejlot, Thank you. I have put it on a separate line because I believe there is some catch about the set being created every time or something. – sshashank124 Jul 06 '14 at 13:43
Lists cannot be hashed... – thefourtheye Jul 06 '14 at 13:53
@thefourtheye, Apologies, My bad. – sshashank124 Jul 06 '14 at 13:54
Worst case complexity is O(N ^ 2), whereas my solution is O(N + M) – thefourtheye Jul 06 '14 at 13:55

thefourtheye · Accepted Answer · 2014-07-06T14:14:01.137

The other solution runs in O(N^2), where as this solution runs in O(N + M) time complexity.

x1 = [["x1", "y1"], ["x1", "x2"]]
x2 = [["x1", "y1"], ["x1", "x2"], ["x2", "y2"]]
set1 = {tuple(item) for item in x1}
print [item for item in x2 if tuple(item) not in set1]
# [['x2', 'y2']]

Just convert the first set of items to a list of tuples and then create a set with the tuples. Then, for every item in the next list of lists, convert that to a tuple and check if it is not there in the set.

How can I get the difference between two lists?

2 Answers2