NEXT K-SET OF N-SET

NEXT K-SET OF N-SET (LET)

Let Subcommand

Generate the next k-set of a an n-set.

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

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.

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.

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.

LET N = 5
LET K = 3
LET Y = NEXT K-SET OF N-SET K N

Dataplot implements this command using the algorithm NEXKSB 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 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.

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 COMPOSITION	= Generate the next composition.
NEXT PARTITION	= Generate the next partition.
NEXT EQUIVALENCE RELATION	= Generate the next composition.

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

Combinatorial Analysis

2009/1

 
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