2

I need to find the difference between two lists for a problem i am trying to solve.

For example if:

list1 = ["Johny", "Lisa", "Madison", "Kirean"]
list2 = ["Lisa", "Madison", "Kirean"]
print difference(list1, list2)
#Should return ["Johnny"]

I have tried two different methods.

One was looping through the list and checking for similar elements and removing similar elements. Which took too long to compile for half the cases.

The other way was using subtracting sets. But this approach returned nothing in some of the cases.(Those cases were solved by the first solution if they were within the time limit.)

Is there any other way that would be invincible and also fast enough?

This is the link to the problem: http://www.dmoj.ca/problem/coci14c2p2

And here is my code:

a = []
b = []
n = input()
for i in range(n):
    a.append(raw_input())
for i in range(n-1):
    b.append(raw_input())

print list(set(a) ^ set(b))[0]
Mehdi Alali
  • 163
  • 1
  • 11
  • 2
    Relevant: http://stackoverflow.com/questions/3462143/get-difference-between-two-lists – FourScore Jan 06 '15 at 02:40
  • What do you want `difference(['a','b','c'], ['b','c','d'])` to return? Do you want the symmetric difference (i.e ['a','d'])`? Do you care about order? – DSM Jan 06 '15 at 02:45
  • "all cases" is a lot simpler if the items are all hashable (strings are of course) – John La Rooy Jan 06 '15 at 02:49
  • @DSM It is guaranteed that all items in list2 are within list1 – Mehdi Alali Jan 06 '15 at 02:52
  • Now that's strange, because the only case I can think of in which subtracting sets should fail for you is if there are elements in `list2` you wanted to see which weren't in `list1`. If all the elements of `list2` are in `list1`, there should be no difference between `set(list1) - set(list2)` and `set(list1) ^ set(list2)`. – DSM Jan 06 '15 at 02:58
  • The only thing I know about those cases is that they return nothing. – Mehdi Alali Jan 06 '15 at 03:12

4 Answers4

2

You can use set and symmetric_difference(), i.e. finding the elements that are in exactly one of the sets:

list1 = ["Johny", "Lisa", "Madison", "Kirean"]
list2 = ["Lisa", "Madison", "Kirean"]
list(set(list1).symmetric_difference(list2))
# Output: ['Johny']

Note that if difference() is used, the output will be empty if list1 and list2 are swapped.

YS-L
  • 14,358
  • 3
  • 47
  • 58
2

as @YS-L mentioned, set.symmetric_difference is what you need, but not set.difference. Also, you can use operator ^ instead:

In [108]: set(list2) ^ set(list1)
Out[108]: {'Johny'}

In [109]: set(list1).symmetric_difference(list2)
Out[109]: {'Johny'}
zhangxaochen
  • 32,744
  • 15
  • 77
  • 108
1

you need to use set:

>>> list1 = ["Johny", "Lisa", "Madison", "Kirean"]
>>> list2 = ["Lisa", "Madison", "Kirean"]
>>> list(set(list1) - set(list2))
['Johny']
Hackaholic
  • 19,069
  • 5
  • 54
  • 72
  • If order doesn't matter, this is a great way to do it. You could also sort them and use something like the merge step of mergesort, especially if the sets are too big to fit into RAM. – dstromberg Jan 06 '15 at 02:44
  • @MehdiAlali update ur realtime output so we can understand better – Hackaholic Jan 06 '15 at 02:46
  • If you do `list(set(list2)-set(list1))` you get an empty set. `symmetric_difference` fixes it. Just doing the difference returns everything in the first but not the second. So if first is a subset of second, it returns empty. – Joel Jan 06 '15 at 02:59
0

What about:

set1 = set(list1)
set2 = set(list2)

result = list((set1 | set2) - (set1 & set2))
Scott Harris
  • 319
  • 1
  • 5