Efficient List Subtraction

[Magnus L. Hetland]

"Steven D. Majewski" <sdm7g at Virginia.EDU> writes:

> On Fri, 23 Apr 1999, KELLEY SCOTT T wrote:
> 
> > 
> > Does anyone out there have a simple way to compare two lists (some operator perhaps) and
> > return
> > a list of *differences*?  By differences, I mean the following:  If had two
> > lists  like,
[...]
> 
> Well -- it's probably not the most efficient, but the simplest 
> list intersection  is probably:

OK... Posted an efficient version earlier -- now for the simple ones...

(Assuming that there are no duplicates in the original lists...)

> 
> >>> a = [1,4,5,100]
> >>> b = [4,5]
> >>> filter( lambda x: x in a, b )
> [4, 5]
> >>> filter( lambda x: x in b, a )		# order doesn't matter
> [4, 5]						# for intersection
> 
> 					# but it does for set-difference
> >>> filter( lambda x: x not in a, b )		# b - a 
> []
> >>> filter( lambda x: x not in b, a )		# a - b 
> [1, 100]
> 
> I don't think union or XOR can be done as concisely. 

Let's do union first:

>>> a + filter(lambda x: x not in a, b)

Then XOR:

>>> filter(lambda x: x not in b, a) + filter(lambda x: x not in a, b)

*If* we had an xor operator, we might say:

>>> filter(lambda x: x in a xor x in b, a+b)

Even though we don't, we might settle for:

>>> filter(lambda x: (x in a and not (x in b)) or \
    (x in b and not (x in a)), a+b)

Or, actually:

>>> filter(lambda x: not (x in a and x in b), a+b)

Not too bad, is it?

--
               > Hi! I'm the signature virus 99!
  Magnus       > Copy me into your signature and join the fun!
  Lie
  Hetland        http://arcadia.laiv.org <arcadia at laiv.org>