NEXT COMPOSITION

NEXT COMPOSITION (LET)

Let Subcommand

Generate the next composition of a positive integer.

Given positive integers n and k, a composition of n into k parts is defined as
n = r₁ + r₂ + ... + r_k (r_i ≥ 0, i = 1,k)

(the order of r₁, ..., r_k 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.

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.

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.

LET N = 5
LET K = 3
LET Y = NEXT COMPOSITION K N

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

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

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

Combinatorial Analysis

2009/1

 
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