SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
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: 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
Please email comments on this WWW page to alan.heckert@nist.gov.