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 K-SET OF N-SET

Name:
    NEXT K-SET OF N-SET (LET)
Type:
    Let Subcommand
Purpose:
    Generate the next k-set of a an n-set.
Description:
    Given a set of n elements {1, 2, ..., n}, a basic combinatorial problem is the combination of n things taken k at a time. For a given n and k, there are

      (n k)  = n!/[k!*(n-k)!]    n >= k

    k-sets of the original n-set.

    This command can be used to generate all of these k-sets of an n-set for given values of n and k. Each time this command is called for given values of n and k, the next k-set of an n-set is returned. Note that the first call with given values of n and k has a slightly different syntax than the subsequent calls since the subsequent calls need to specify the most recent k-set of an n-set generated.

    The output is an array of size k that identifies the elements included in the k-set of an n-set.

Syntax 1:
    LET <y> = NEXT K-SET OF N-SET <k> <n>
    where <k> is a number or parameter that specifies the size of the k-set;
                <n> is a number or parameter that specifies the number of elements in the set;
    and      <y> is a variable where the k-set of an n-set is saved.

    This syntax is used to return the first k-set of an n-set in the sequence of k-sets of an n-set.

Syntax 2:
    LET <y> = NEXT K-SET OF N-SET <k> <n> <yprev>
    where <k> is a number or parameter that specifies the size of the k-set;
                <n> is a number or parameter that specifies the number of elements in the set;
                <yprev> is a variable which contains the most recent k-set of an n-set;
    and      <y> is a variable where the k-set of an n-set is saved.

    This syntax is used to return all k-sets of an n-set in the sequence of k-sets of an n-set after the first k-set of an n-set has been generated.

Examples:
    LET N = 5
    LET K = 3
    LET Y = NEXT K-SET OF N-SET K N
Note:
    Dataplot implements this command using the algorithm NEXKSB 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 k-set of an n-set is the last k-set of an n-set in the sequence for given values of n and k. Otherwise, the value of LASTSEQU will be set to 0.
Default:
    None
Synonyms:
    None
Related Commands: References:
    Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 3.
Applications:
    Combinatorial Analysis
Implementation Date:
    2009/1
Program:
     
    LET N = 5
    LET K = 3
    LET NTOT = BINOMIAL(N,K)
    SET WRITE REWIND OFF
    SET WRITE DECIMALS 0
    WRITE KSET.OUT "ALL K-SETS OF AN N-SET FOR N = ^N AND K = ^K"
    LET Y = NEXT K-SET OF N-SET K N
    LET YPREV = Y
    WRITE KSET.OUT "K-SET 1:"
    WRITE KSET.OUT Y
    WRITE KSET.OUT " "
    WRITE KSET.OUT " "
    LOOP FOR L = 2 1 NTOT
        LET Y = NEXT K-SET OF N-SET K N YPREV
        WRITE KSET.OUT "K-SET ^L:"
        WRITE KSET.OUT Y
        WRITE KSET.OUT " "
        WRITE KSET.OUT " "
        LET YPREV = Y
    END OF LOOP
        
    The file KSET.OUT contains
    ALL K-SETS OF AN N-SET FOR N = 5 AND K = 3
    K-SET 1:
              1
              2
              3
     
     
    K-SET 2:
              1
              2
              4
     
     
    K-SET 3:
              1
              2
              5
     
     
    K-SET 4:
              1
              3
              4
     
     
    K-SET 5:
              1
              3
              5
     
     
    K-SET 6:
              1
              4
              5
     
     
    K-SET 7:
              2
              3
              4
     
     
    K-SET 8:
              2
              3
              5
     
     
    K-SET 9:
              2
              4
              5
     
     
    K-SET 10:
              3
              4
              5
        

Date created: 1/21/2009
Last updated: 1/21/2009
Please email comments on this WWW page to alan.heckert@nist.gov.