calc: Set Operations
10.6 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 equaled 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.
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. 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).
Info Catalog
calc: Vector and Matrix Arithmetic
calc: Matrix Functions
calc: Statistical Operations