UBB.Developers Forums Community Development Programming PHP and Server-side Scripting Computing set union and intersection

Suppose I have two arrays of positive integers, @one and @two, potentially containing several thousand elements.

I want to compute the array @inter which contains those elements which are in both @one and @two, and the array @union which contains those elements which are in either @one or @two.

Here's my first cut at doing this:

intersection: Pick one of the arrays, put the other in a hash with duumy values, and loop through the first array, adding the elements which are also in the other array to @inter.


union: Put both arrays in the same hash with dummy values, so duplicates are ignored, then extract the keys.


Does anyone know a better way of doing this?

IIRC, there is an example of an intersection in the perl documentation

perldoc -q intersection

I'm also positive I've seen Union and Intersection stuff in the Mastering Algorithms with Perl book, which I don't happen to have accesable at the moment, or I would dig them out for you.

You may wanna check the O'Reilly ftp site and see if there are any source code examples from the Algorithm book there. Perhaps the union/intersection code is given in there.

As for my own methods, I don't often do those, so don't have anything to offer without constructing something. when I've had to do it with hashes though, i've used hash slices.

--mark

Thanks, Mark

I had searched perldoc for "set", but didn't think to look for "intersection".

"perl -q intersection" does include a method for computing the intersection, as well as the union and symmetric difference, and looks nicer than my approach. It also looks like it generalizes easily to more than two sets.

Very cool! Glad the info helped

(btw, im interested to see if you get some cool 1 liner replies in response to your usenet post in c.l.p.moderated too ;))

[edit looks like you got a reply about using a hash slice :)]

--mark

[ April 18, 2001 12:24 AM: Message edited by: Mark Badolato ]