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

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:
 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.
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