Post History

First store the universe of potential elements as a sequence, then encode each set as an *unsigned integer* interpreted as follows: if the 1s bit in binary is set (1), the set contains the 0th element in the universe sequence; if the 2s bit is set, the set contains the 1st element; if the 4s bit, the 2nd element; and so on. (If the universe needs to contain more elements than there are bits in the machine word size, big-integer support will be needed; or the relevant aspects can be emulated with a simple array of integers.)

To identify the contents of a set, iterate over the sequence while testing bits from the integer, and output the appropriate ones.

To check whether a set contains a given element, just check the corresponding bit. (In order to do this starting with the actual element, rather than an index into the universe sequence, a lookup will be needed; it may therefore be a good idea to also build a dictionary mapping from elements to indices.)

Set unions turn into bitwise-or operations, and set intersections into bitwise-and operations; similarly for (symmetric) differences and so on.

As an added bonus, enumerating the powerset of the universe of elements is trivial: just count upwards from 0 to 2<sup>n</sup>.