set_theory

set_theory, a C code which implements some of the operations of set theory.

We assume that a set is represented by a strictly ascending sequence of positive integers. We might think of a universal set U = 1 : N in cases where all our subsets will have elements between 1 and N.

Set theoretic operations include:

• definition using a numeric property: A = find ( mod ( U, 3 ) = 1 );
• definition using an explicit list: A = [ 1, 3, 8];
• unique: creating a set from the unique elements of a list: A = unique ( [ 1, 3, 8, 3, 3, 1, 7, 3, 1, 1 ] );
• union: C = union ( A, B );
• intersection: C = intersect ( A, B );
• symmetric difference: C = setxor ( A, B );
• complement with respect to the universal set: B = setdiff ( U, A );
• complement with respect to another set: C = setdiff ( B, A );
• cardinality: n = length ( A );
• membership: true/false = ismember ( a, A );
• subset: true/false = ismember ( B, A );
• addition of one element: A = unique ( [ A; a ] );
• deletion of one element: A = setxor ( A, a );
• indexing one element: i = find ( A == a );

Although sets are traditionally allowed to contain arbitrary elements, it is computationally convenient to assume that our sets are simply subsets of the integers from 1 to N.

If N is no greater than 32, we can represent a set using a 32 bit integer. We term this the B4SET representation. It is compact, but as it stands, is limited to a universal set of no more than 32 elements.

Assuming we can regard the integer as an unsigned quantity, each bit of the binary representation of the integer represents the presence (1) or absence (0) of the corresponding integer in the set. Thus, assuming N is 5, the set { 1, 2, 5} corresponds to the binary representation 10011 and hence to the integer 19. In order to read or write the individual bits of an integer, the functions BTEST, IBCLR and IBSET are useful in this case.

A more flexible, but less efficient, representation of sets uses a logical vector, and is called the LSET representation. Assuming we have a universal set of N elements, any set is represented by a logical vector of N elements, the I-th element of which is TRUE if I is an element of the set.

A representation that can be more efficient for small subsets of a large universal set is the I4SET. In this representation, we simply list, in ascending order, the elements of the set. The representation is simple, but manipulation is more involved. For instance, to create the union of two sets, we must determine the number of unique elements in the two component sets, allocate the necessary space, then interleave the elements of the two components appropriately.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

set_theory is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

COMBO, a C code which handles combinatorial problems, by Kreher and Stinson;

set_theory_test

SUBSET, a C code which ranks, unranks, and generates random subsets, combinations, permutations, and so on;

Reference:

1. Charles Pinter,
   Set Theory,
   Addison-Wesley, 1971,
   LC: QA248.P55.

Source Code:

• set_theory.c, the source code.
• set_theory.sh, compiles the source code.
• set_theory.h, the include file.