[erlang-questions] working with sets

[David Holz]

From: vances@REDACTED
> Can one of you CS wizzes point me at the best way to
> maintain a set of sets where all elements of all sets
> must be unique? I don't need a really big data set
> but rolling my own with the list module feels wrong.
>
> For example {{1,2,3},{4,5,6},{7,8,9}} is a valid set.
> Trying to enter {9,10,11} should fail.

I might base it on a dict, mapping a value to which set number (or name, or whatever) it's in.  That way a value only points to a single set at a time.  You could also easily query which set a value is in (or if a value is any set) just by dict:find/2.

The data above would map to something like this:

  dict:from_list([{1,1},{2,1},{3,1},{4,2},{5,2},{6,2},{7,3},{8,3},{9,3}]).

Adding a new set would require getting the next set ID, then adding each element as a key with the ID as the value.  If a key already exists, (like the 9 in adding [9,10,11] (I'd say use lists [] instead of tuples {} for this)) then the insert fails.

To retrieve a set by its ID, you could use dict:fold( , [], SetDictThing ).

I think it would do everything you want, though there's a lot of iteration in terms of runtime speed.  The dict does support your notion of enforcing a single instance per value which is why I thought of this, but it might end up that doing your own list-based checks might be shorter code.  It also depends on where you want to optimize your runtime speed.  The dict-based one lets you do checks very quickly, but the fetch/store of sets might be slower.
_________________________________________________________________
Put your friends on the big screen with Windows Vista® + Windows Live™.
http://www.microsoft.com/windows/shop/specialoffers.mspx?ocid=TXT_TAGLM_CPC_MediaCtr_bigscreen_012008