NEXT EQUIVALENCE RELATION

NEXT EQUIVALENCE RELATION (LET)

Let Subcommand

Generate the next equivalence relation of a an n-element set.

Given a set S = {1, 2, ..., n}, a partition of S is defined as a collection of sets T₁, T₂, ... , T_k satisfying
1. The intersection of T_i and T_j is the empty set for i ≠ j.

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 T_i as the equivalence classes.

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.

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.

LET N = 5
LET Y = NEXT EQUIVALENCE RELATION

Dataplot implements this command using the NEXEQU algorithm described in Nijenhuis and Wilf (see Reference section below).

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.

None

None

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.

Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 11.

Combinatorial Analysis

2009/1

 
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