NEXT PARTITION

NEXT PARTITION (LET)

Let Subcommand

Generate the next partition of a positive integer.

Given a positive integer n, a partition of n is defined as
n = r₁ + r₂ + ... + r_k (r₁ ≥ r₂ ≥ ...≥ r_k)

where r₁, r₂, ...., r_k are positive integers.

For example, if n = 6, then there are 3 partitions with 3 elements:

        6 = 4 + 1 + 1
          = 3 + 2 + 1
          = 2 + 2 + 2
    

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

The output is a pair of vectors. The first vector contains the integers in the partition while the second vector contains the number of times the corresponding integer in the first vector is contained in the partition.

LET <yval> <yrepeat> = NEXT PARTITION <n>
where <n> is a number or parameter that specifies the size of the set;
            <yval> is a variable containing the values for the current permutation;
and      <yrepeat> is a variable containing the repeat values for the current permutation.

This syntax is used to return the first partition in the sequence of partitions.

LET <yval> <yrepeat> = NEXT PARTITION <n> <yvalold> <yrepold>
where <n> is a number or parameter that specifies the size of the set;
            <yvalold> is a variable that contains the most recently generated values for the given value of <n>;
            <yrepold> is a variable that contains the most recently generated repeat values for the given value of <n>;
            <yval> is a variable containing the values for the current permutation;
and      <yrepeat> is a variable containing the repeat values for the current permutation.

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

LET N = 6
LET YVAL2 YREPEAT2 = NEXT PARTITION N
LET YVAL1 YREPEAT1 = NEXT PARTITION N YVAL2 YREPEAT2

Dataplot implements this command using the NEXPAR 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 partition is the last partition in the sequence for the given value of n.

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

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

Combinatorial Analysis

2009/1

 
LET N = 3
SET WRITE REWIND OFF
SET WRITE DECIMALS 0
WRITE PARTITION.OUT "PARTITIONS FOR N = 3"
LET Y YREP = NEXT PARTITION N
LET YPREV    = Y
LET YREPPREV = YREP
WRITE PARTITION.OUT "PARTITION 1:"
WRITE PARTITION.OUT Y YREP
WRITE PARTITION.OUT " "
WRITE PARTITION.OUT " "
LET NUMPAR = 1
LOOP FOR K = 2 1 10
    LET NUMPAR = NUMPAR + 1
    LET Y YREP = NEXT PARTITION N YPREV YREPPREV
    WRITE PARTITION.OUT "PARTITION ^K:"
    WRITE PARTITION.OUT Y YREP
    WRITE PARTITION.OUT " "
    WRITE PARTITION.OUT " "
    DELETE YPREV YREPPREV
    LET YPREV    = Y
    LET YREPPREV = YREP
    DELETE Y YREP
    IF LASTSEQU = 1
       BREAK LOOP
    END OF IF
END OF LOOP
WRITE PARTITION.OUT "NUMBER OF PARTITIONS: ^NUMPAR"
    

The file PARTITION.OUT contains

PARTITIONS FOR N = 3
PARTITION 1:
          3              1
 
 
PARTITION 2:
          2              1
          1              1
 
 
PARTITION 3:
          1              3
 
 
NUMBER OF PARTITIONS: 3