Dataplot Vol 2 Vol 1

# NEXT EQUIVALENCE RELATION

Name:
NEXT EQUIVALENCE RELATION (LET)
Type:
Let Subcommand
Purpose:
Generate the next equivalence relation of a an n-element set.
Description:
Given a set S = {1, 2, ..., n}, a partition of S is defined as a collection of sets T1, T2, ... , Tk satisfying

1. The intersection of Ti and Tj is the empty set for ij.

2. The union of all k sets contains all the elements of S.

For example, if n = 3, then there are 5 possible partitions:

{1, 2, 3}
{1,2} {3}
{1, 3} {2}
{2, 3} {1}
{1} {2} {3}

The output of this command is an array of size n where the ith element identifies the class which i belongs to. For example, the following array (for n = 5)

3 3 1 2 2

identifies the partition

{3} {4, 5} {1, 2}

A partition of a set is identical with an equivalence relation on the set with the Ti as the equivalence classes.

Syntax 1:
LET <y> <yp> = NEXT EQUIVALENCE RELATION <n>
where <n> is a number or parameter that specifies the size of the original set;
<yp> is a variable that contains the number of elements in the ith classs of the output partition;
and      <y> is a variable where the equivalence relation is saved.

This syntax is used to return the first equivalence relation in the sequence of equivalence relation.

The <yp> values are not of primary interest. They are returned because the current values of this array are needed in computing the next equivalence relation in the sequence.

Syntax 2:
LET <y> <yp> = NEXT EQUIVALENCE RELATION <n> <yprev> <ypold>
where <n> is a number or parameter that specifies the size of the original set;
<yprev> is a variable that contains the most recently generated values for the given value of <n>;
<ypold> is a variable that contains the most recently generated values for the <yp> variable;
<yp> is a variable that contains the number of elements in the ith classs of the output partition;
and      <y> is a variable where the equivalence relation is saved.

This syntax is used to return the all equivalence relations in the sequence of equivalence relations after the first equivalence relation has been generated.

The <yp> values are not of primary interest. They are returned because the current values of this array are needed in computing the next equivalence relation in the sequence.

Examples:
LET N = 5
LET Y = NEXT EQUIVALENCE RELATION
Note:
Dataplot implements this command using the NEXEQU algorithm described in Nijenhuis and Wilf (see Reference section below).
Note:
Dataplot saves the internal parameter LASTSEQU when this command is entered. If LASTSEQU = 1, this indicates that the current equivalence relation is the last equivalence relation in the sequence for the given value of n.
Default:
None
Synonyms:
None
Related Commands:
 LET = Generate data transformations. RANDOM PERMUTATION = Generate a random permutation. RANDOM K-SET OF N-SET = Generate a random k-set of n-set. RANDOM COMPOSITION = Generate a random composition. RANDOM PARTITION = Generate a random partition. RANDOM SUBSET = Generate a random subset. RANDOM EQUIVALENCE RELATION = Generate a random equivalence relation. NEXT SUBSET = Generate the next subset of a set. NEXT PERMUTATION = Generate the next permutation. NEXT K-SET OF N-SET = Generate the next k-set of n-set. NEXT COMPOSITION = Generate the next composition. NEXT PARTITION = Generate the next partition.
Reference:
Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 11.
Applications:
Combinatorial Analysis
Implementation Date:
2009/1
Program:
```
LET N = 5
SET WRITE REWIND OFF
WRITE EQUIVALENCE.OUT "EQUIVALENCE RELATIONS FOR N = 5"
LET Y YP = NEXT EQUIVALENCE RELATION N
LET YPREV = Y
LET YPOLD = YP
WRITE EQUIVALENCE.OUT "EQUIVALENCE RELATION 1:"
WRITE EQUIVALENCE.OUT Y
WRITE EQUIVALENCE.OUT " "
WRITE EQUIVALENCE.OUT " "
LET NUMEQUIV = 1
LOOP FOR K = 2 1 100
LET NUMEQUIV = NUMEQUIV + 1
. LET Y YP = NEXT EQUIVALENCE RELATION N YPREV YPOLD
LET Y YP = NEXT EQUIVALENCE RELATION N YPREV YPOLD
WRITE EQUIVALENCE.OUT "EQUIVALENCE RELATION ^K:"
WRITE EQUIVALENCE.OUT Y
WRITE EQUIVALENCE.OUT " "
WRITE EQUIVALENCE.OUT " "
DELETE YPREV YPOLD
LET YPREV = Y
LET YPOLD = YP
DELETE Y YP
IF LASTSEQU = 1
BREAK LOOP
END OF IF
END OF LOOP
WRITE EQUIVALENCE.OUT "NUMBER OF EQUIVALENCE RELATIONS: ^NUMEQUIV"
```
The file EQUIVALENCE.OUT contains
`    `

Date created: 1/21/2009
Last updated: 1/21/2009