Dataplot Vol 2 Vol 1

# NEXT COMPOSITION

Name:
NEXT COMPOSITION (LET)
Type:
Let Subcommand
Purpose:
Generate the next composition of a positive integer.
Description:
Given positive integers n and k, a composition of n into k parts is defined as

n = r1 + r2 + ... + rk (ri ≥ 0, i = 1,k)

(the order of r1, ..., rk is significant).

The number of compositions is given by

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

The output is an array of size k.

Syntax 1:
LET <y> = NEXT COMPOSITION <k> <n>
where <k> is a number or parameter that specifies the number of elements in the composition;
<n> is a number or parameter that specifies the integer for which the composition is being generated;
and      <y> is a variable where the composition is saved.

This syntax is used to return the first composition in the sequence of compositions.

Syntax 2:
LET <y> = NEXT COMPOSITION <k> <n> <yprev>
where <k> is a number or parameter that specifies the number of elements in the composition;
<n> is a number or parameter that specifies the integer for which the composition is being generated;
<yprev> is a variable which contains the most recent composition;
and      <y> is a variable where the composition is saved.

This syntax is used to return the all compositions in the sequence of compositions after the first composition has been generated.

Examples:
LET N = 5
LET K = 3
LET Y = NEXT COMPOSITION K N
Note:
Dataplot implements this command using the NEXCOM 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 composition is the last composition in the sequence for the 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 K-SET OF N-SET = Generate the next k-set of n-set. NEXT PARTITION = Generate the next partition. NEXT EQUIVALENCE RELATION = Generate the next composition.
Reference:
Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 5.
Applications:
Combinatorial Analysis
Implementation Date:
2009/1
Program:

LET N = 6
LET K = 3
SET WRITE REWIND OFF
SET WRITE DECIMALS 0
WRITE COMPOSITION.OUT "COMPOSITIONS FOR N = 3"
LET Y = NEXT COMPOSITION K N
LET YPREV = Y
WRITE COMPOSITION.OUT "COMPOSITION 1:"
WRITE COMPOSITION.OUT Y
WRITE COMPOSITION.OUT " "
WRITE COMPOSITION.OUT " "
LET NUMCOMP = 1
LOOP FOR L = 2 1 30
LET NUMCOMP = NUMCOMP + 1
LET Y = NEXT COMPOSITION K N YPREV
WRITE COMPOSITION.OUT "COMPOSITION ^L:"
WRITE COMPOSITION.OUT Y
WRITE COMPOSITION.OUT " "
WRITE COMPOSITION.OUT " "
LET YPREV    = Y
IF LASTSEQU = 1
BREAK LOOP
END OF IF
END OF LOOP
WRITE COMPOSITION.OUT "NUMBER OF COMPOSITIONS: ^NUMCOMP"

The file COMPOSITION.OUT contains
COMPOSITIONS FOR N = 3
COMPOSITION 1:
6
0
0

COMPOSITION 2:
5
1
0

COMPOSITION 3:
4
2
0

COMPOSITION 4:
3
3
0

COMPOSITION 5:
2
4
0

COMPOSITION 6:
1
5
0

COMPOSITION 7:
0
6
0

COMPOSITION 8:
5
0
1

COMPOSITION 9:
4
1
1

COMPOSITION 10:
3
2
1

COMPOSITION 11:
2
3
1

COMPOSITION 12:
1
4
1

COMPOSITION 13:
0
5
1

COMPOSITION 14:
4
0
2

COMPOSITION 15:
3
1
2

COMPOSITION 16:
2
2
2

COMPOSITION 17:
1
3
2

COMPOSITION 18:
0
4
2

COMPOSITION 19:
3
0
3

COMPOSITION 20:
2
1
3

COMPOSITION 21:
1
2
3

COMPOSITION 22:
0
3
3

COMPOSITION 23:
2
0
4

COMPOSITION 24:
1
1
4

COMPOSITION 25:
0
2
4

COMPOSITION 26:
1
0
5

COMPOSITION 27:
0
1
5

COMPOSITION 28:
0
0
6

NUMBER OF COMPOSITIONS: 28

Date created: 1/21/2009
Last updated: 1/21/2009