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.
No comments :
Post a Comment