Set Operations using Vectors
============================

Calc includes several commands which interpret vectors as "sets" of
objects.  A set is a collection of objects; any given object can
appear only once in the set.  Calc stores sets as vectors of objects
in sorted order.  Objects in a Calc set can be any of the usual
things, such as numbers, variables, or formulas.  Two set elements are
considered equal if they are identical, except that numerically equal
numbers like the integer 4 and the float 4.0 are considered equal even
though they are not "identical."  Variables are treated like plain
symbols without attached values by the set operations; subtracting the
set `[b]' from `[a, b]' always yields the set `[a]' even though if the
variables `a' and `b' both equalled 17, you might expect the answer
`[]'.

If a set contains interval forms, then it is assumed to be a set of
real numbers.  In this case, all set operations require the elements
of the set to be only things that are allowed in intervals: Real
numbers, plus and minus infinity, HMS forms, and date forms.  If there
are variables or other non-real objects present in a real set, all set
operations on it will be left in unevaluated form.

If the input to a set operation is a plain number or interval form A,
it is treated like the one-element vector `[A]'.  The result is always
a vector, except that if the set consists of a single interval, the
interval itself is returned instead.

See Logical Operations, for the `in' function which tests if
a certain value is a member of a given set.  To test if the set `A' is
a subset of the set `B', use `vdiff(A, B) = []'.

The `V +' (`calc-remove-duplicates') [`rdup'] command converts an
arbitrary vector into set notation.  It works by sorting the vector as
if by `V S', then removing duplicates.  (For example, `[a, 5, 4, a,
4.0]' is sorted to `[4, 4.0, 5, a, a]' and then reduced to `[4, 5,
a]').  Overlapping intervals are merged as necessary.  You rarely need
to use `V +' explicitly, since all the other set-based commands apply
`V +' to their inputs before using them.

The `V V' (`calc-set-union') [`vunion'] command computes the union of
two sets.  An object is in the union of two sets if and only if it is
in either (or both) of the input sets.  (You could accomplish the same
thing by concatenating the sets with `|', then using `V +'.)

The `V ^' (`calc-set-intersect') [`vint'] command computes the
intersection of two sets.  An object is in the intersection if and
only if it is in both of the input sets.  Thus if the input sets are
disjoint, i.e., if they share no common elements, the result will be
the empty vector `[]'.  Note that the characters `V' and `^' were
chosen to be close to the conventional mathematical notation for set
union and intersection.

The `V -' (`calc-set-difference') [`vdiff'] command computes the
difference between two sets.  An object is in the difference `A - B'
if and only if it is in `A' but not in `B'.  Thus subtracting `[y,z]'
from a set will remove the elements `y' and `z' if they are present.
You can also think of this as a general "set complement" operator; if
`A' is the set of all possible values, then `A - B' is the
"complement" of `B'.  Obviously this is only practical if the set of
all possible values in your problem is small enough to list in a Calc
vector (or simple enough to express in a few intervals).

The `V X' (`calc-set-xor') [`vxor'] command computes the
"exclusive-or," or "symmetric difference" of two sets.  An object is
in the symmetric difference of two sets if and only if it is in one,
but *not* both, of the sets.  Objects that occur in both sets "cancel
out."

The `V ~' (`calc-set-complement') [`vcompl'] command computes the
complement of a set with respect to the real numbers.  Thus
`vcompl(x)' is equivalent to `vdiff([-inf .. inf], x)'.  For example,
`vcompl([2, (3 .. 4]])' evaluates to `[[-inf .. 2), (2 .. 3], (4
.. inf]]'.

The `V F' (`calc-set-floor') [`vfloor'] command reinterprets a set as
a set of integers.  Any non-integer values, and intervals that do not
enclose any integers, are removed.  Open intervals are converted to
equivalent closed intervals.  Successive integers are converted into
intervals of integers.  For example, the complement of the set `[2, 6,
7, 8]' is messy, but if you wanted the complement with respect to the
set of integers you could type `V ~ V F' to get `[[-inf .. 1], [3
.. 5], [9 .. inf]]'.

The `V E' (`calc-set-enumerate') [`venum'] command converts a set of
integers into an explicit vector.  Intervals in the set are expanded
out to lists of all integers encompassed by the intervals.  This only
works for finite sets (i.e., sets which do not involve `-inf' or
`inf').

The `V :' (`calc-set-span') [`vspan'] command converts any
set of reals into an interval form that encompasses all its elements.
The lower limit will be the smallest element in the set; the upper
limit will be the largest element.  For an empty set, `vspan([])'
returns the empty interval `[0 .. 0)'.

The `V #' (`calc-set-cardinality') [`vcard'] command counts the number
of integers in a set.  The result is the length of the vector that
would be produced by `V E', although the computation is much more
efficient than actually producing that vector.

Another representation for sets that may be more appropriate in some
cases is binary numbers.  If you are dealing with sets of integers
in the range 0 to 49, you can use a 50-bit binary number where a
particular bit is 1 if the corresponding element is in the set.
See Binary Functions, for a list of commands that operate on
binary numbers.  Note that many of the above set operations have
direct equivalents in binary arithmetic: `b o' (`calc-or'), `b a'
(`calc-and'), `b d' (`calc-diff'), `b x' (`calc-xor'), and `b n'
(`calc-not'), respectively.  You can use whatever representation for
sets is most convenient to you.

The `b u' (`calc-unpack-bits') [`vunpack'] command converts an integer
that represents a set in binary into a set in vector/interval
notation.  For example, `vunpack(67)' returns `[[0 .. 1], 6]'.  If the
input is negative, the set it represents is semi-infinite:
`vunpack(-4) = [2 .. inf)'.  Use `V E' afterwards to expand intervals
to individual values if you wish.  Note that this command uses the `b'
(binary) prefix key.

The `b p' (`calc-pack-bits') [`vpack'] command converts the other way,
from a vector or interval representing a set of nonnegative integers
into a binary integer describing the same set.  The set may include
positive infinity, but must not include any negative numbers.  The
input is interpreted as a set of integers in the sense of `V F'
(`vfloor').  Beware that a simple input like `[100]' can result in a
huge integer representation (`2^100', a 31-digit integer, in this
case).