Part 6: Efficiently Representing Sets - Continued...

· Read in about 1 min · (148 words) ·

Great article. Gives some very valuable information on implementing sets with a finite universe.

It doesn’t suit my requirements - I need to represent sets where the universal set might be infinite - like, say the set of strings.

The trouble starts with trying to implement the set complement operation - you can’t obviously list an infinite set, so the trick is to represent it as a cofinite set. I haven’t really read up on cofinite sets, but the layman definition goes as

'A set whose complement is finite'

Well that’s it. So keep a flag with the data structure to indicate a set complement.

The ElementOf operation is trivial to implement. Subset is trickier and so’s union, intersection and difference.

I just completed a bare bones implementation using a hashmap. All the tests are working (got 20 of them). You can find it here ifĂ‚ you’re interested.