|
[_____]
Instead of using a loop to apply the same binary associative operator
to all elements of a (non-formal) set, it is in certain cases possible
to use the reduction operator &.
& o S : Op, SetIndx -> Elt
& o S : Op, SetMulti -> Elt
Given an enumerated, indexed, or multiset
S = { a1, a2, ..., an } of
elements belonging to an algebraic structure U, and an
(associative) operator  : U x U -> U,
form the element
ai1 ai2 ai3 ... ain,
for some permutation i1, ..., in of 1, ..., n.
Currently, the following operators may be used to reduce such sets:
+, *, and, or, join, and meet.
An error will occur if the operator is not defined on U.
If S contains a single element a, then the value returned
is a. If S is the null set (empty and no universe specified)
or S is empty with universe U (and the operation is defined in U),
then the
result (or error) depends on the operation and upon U.
The following table defines the return value:
EMPTY NULL
&+ U!0 error
&* U!1 error
&and true true
&or false false
&join empty null
&meet error error
Warning: since the reduction may take place in an arbitrary order
on the arguments a1, ..., an, the result is not unambiguously defined
if the operation is not commutative on the arguments!
The function choose defined below takes a set S and an integer k
as input, and produces a set of all subsets of S with cardinality k.
> function choose(S, k)
> if k eq 0 then
> return { { } };
> else
> return &join{ { s join { x } : s in choose(S diff { x }, k-1) } : x in S };
> end if;
> end function;
So, for example:
> S := { 1, 2, 3, 4 };
> choose(S, 2);
{
{ 1, 3 },
{ 1, 4 },
{ 2, 4 },
{ 2, 3 },
{ 1, 2 },
{ 3, 4 }
}
Try to guess what happens if k < 0.
The iteration operator in can be used in loops or in the set and
sequence constructors to enumerate elements of a set.
Enumerated, indexed, and multisets allow enumeration of their elements;
formal sets do not.
For indexed sets the enumeration will occur according to the order given
by the indexing.
Enumerate the elements of an enumerated, indexed, or multiset S.
Note that if S is a multiset then each element will be returned a
number of times equal to its multiplicity in S.
Enumerate the elements x of an indexed set S, together with the
corresponding index value i.
Enumerate the elements x of the underlying set of the multiset M,
together with the corresponding multiplicity v.
Note that elements with multiplicity larger than 1 will still only be
returned once by this version of the iterator.
We display a simple frequency count of a certain string.
> M := Multiset(Eltseq("hello world"));
> for letter -> count in M do
> if count eq 1 then
> are := "is"; s := "";
> else
> are := "are"; s := "s";
> end if;
> printf "There %o %o '%o'%o n", are, count, letter, s;
> end for;
There is 1 ' '
There is 1 'e'
There are 3 'l's
There is 1 'w'
There is 1 'h'
There are 2 'o's
There is 1 'd'
There is 1 'r'
Note the difference between the use of the dual iterator above and the
single form below.
> for letter in M do
> printf "'%o'n", letter;
> end for;
' '
'e'
'l'
'l'
'l'
'w'
'h'
'o'
'o'
'd'
'r'
[Next][Prev] [_____] [Left] [Up] [Index] [Root]
|