Part 6: Efficiently Representing Sets – Continued…

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s