SET_THEORY
An Implementation of Set Theoretic Operations

SET_THEORY is a C++ library 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 GNU LGPL license.

Languages:

SET_THEORY is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

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

SUBSET, a C++ library 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.cpp, the source code.
• set_theory.hpp, the include file.
• set_theory.sh, BASH commands to compile the source code.

Examples and Tests:

• set_theory_prb.cpp, a sample calling program.
• set_theory_prb.sh, BASH commands to compile and run the sample program.
• set_theory_prb_output.txt, the output file.

List of Routines:

• B4SET_COLEX_RANK computes the colexicographic rank of a B4SET.
• B4SET_COLEX_SUCCESSOR computes the colexicographic successor of a B4SET.
• B4SET_COLEX_UNRANK computes the B4SET of given colexicographic rank.
• B4SET_COMPLEMENT computes the complement of a B4SET.
• B4SET_COMPLEMENT_RELATIVE computes the relative complement of a B4SET.
• B4SET_DELETE deletes an element from a B4SET.
• B4SET_DISTANCE computes the Hamming distance between two B4SET's.
• B4SET_ENUM enumerates the B4SET's.
• B4SET_INDEX returns the index of an element of a B4SET.
• B4SET_INSERT inserts an item into a B4SET.
• B4SET_INTERSECT computes the intersection of two B4SET's.
• B4SET_IS_EMPTY determines if a B4SET is empty.
• B4SET_IS_EQUAL determines if two B4SET's are equal.
• B4SET_IS_MEMBER determines if an item is a member of a B4SET.
• B4SET_IS_SUBSET determines if one B4SET is a subset of another.
• B4SET_LEX_RANK computes the lexicographic rank of a B4SET.
• B4SET_LEX_SUCCESSOR computes the lexicographic successor of a B4SET.
• B4SET_LEX_UNRANK computes the B4SET of given lexicographic rank.
• B4SET_RANDOM sets a rondom B4SET.
• B4SET_TO_LSET converts a B4SET to an LSET.
• B4SET_TRANSPOSE_PRINT prints a B4SET "transposed".
• B4SET_UNION computes the union of two B4SET's.
• B4SET_WEIGHT computes the Hamming weight of a B4SET.
• B4SET_XOR computes the symmetric difference of two B4SET's.
• DIGIT_TO_CH returns the base 10 digit character corresponding to a digit.
• I4_BCLR clears a bit of an I4.
• I4_BSET sets a bit of an I4.
• I4_BTEST returns a bit of an I4.
• I4_LOG_10 returns the integer part of the logarithm base 10 of an I4.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• I4_POWER returns the value of I^J.
• I4_TO_S converts an I4 to a string.
• I4_WIDTH returns the "width" of an I4.
• I4_XOR xor's a bit of an I4.
• I4VEC_TO_B4SET converts an I4VEC to a B4SET.
• I4VEC_TO_LSET converts an I4VEC to an LSET.
• I4VEC_UNIFORM_NEW returns a scaled pseudorandom I4VEC.
• LSET_COLEX_RANK computes the colexicographic rank of an LSET.
• LSET_COLEX_SUCCESSOR computes the colexicographic successor of an LSET.
• LSET_COLEX_UNRANK computes the LSET of given colexicographic rank.
• LSET_COMPLEMENT computes the complement of an LSET.
• LSET_COMPLEMENT_RELATIVE computes the relative complement of an LSET.
• LSET_DELETE deletes an element from an LSET.
• LSET_DISTANCE computes the Hamming distance between two LSET's.
• LSET_ENUM enumerates the LSET's.
• LSET_INDEX returns the index of an element of an LSET.
• LSET_INSERT inserts an item into an LSET.
• LSET_INTERSECT computes the intersection of two LSET's.
• LSET_IS_EMPTY determines if an LSET is empty.
• LSET_IS_EQUAL determines if two LSET's are equal.
• LSET_IS_MEMBER determines if an item is a member of an LSET.
• LSET_IS_SUBSET determines if one LSET is a subset of another.
• LSET_LEX_RANK computes the lexicographic rank of an LSET.
• LSET_LEX_SUCCESSOR computes the lexicographic successor of an LSET.
• LSET_LEX_UNRANK computes the LSET of given lexicographic rank.
• LSET_RANDOM sets a rondom LSET.
• LSET_TO_B4SET converts an I4VEC to a B4SET.
• LSET_TRANSPOSE_PRINT prints an LSET "transposed".
• LSET_UNION computes the union of two LSET's.
• LSET_WEIGHT computes the Hamming weight of an LSET.
• LSET_XOR computes the symmetric difference of two LSET's.
• LVEC_TRANSPOSE_PRINT prints an LVEC "transposed".
• R4_NINT returns the nearest integer to an R4.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.