NEXT PERMUTATION

NEXT PERMUTATION (LET)

Let Subcommand

Generate the next permutation of n letters.

For a given value of n, there are n! permuations of the integers 1, 2, ..., n. For example, for n = 3, there are 3*2*1 = 6 permutations:

       1  2  3
       1  3  2
       3  1  2
       3  2  1
       2  3  1
       2  1  3
    

This command can be used to generate all of the permutations for a given value of n. Each time this command is called for a given value of n, the next permutation 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 permutation generated.

The output is an array of size n that contains each of the integers from 1 to n exactly once.

LET <y> = NEXT PERMUTATION <n>
where <n> is a number or parameter that specifies the size of the set;
and      <y> is a variable where the current permutation is saved.

This syntax is used to return the first permutation in the sequence of permutations.

LET <y> = NEXT PERMUTATION <n> <yprev>
where <n> is a number or parameter that specifies the size of the set;
            <yprev> is a variable that contains the most recently generated permutation for the given value of <n>;
and      <y> is a variable where the current permutation is saved.

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

LET Y = NEXT PERMUTATION N
LET Y = NEXT PERMUTATION N YPREV

Dataplot implements this command using the algorithm NEXPER 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 permutation is the last permutation in the sequence for the given value of n. 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 K-SET OF N-SET	= Generate the next k-set of n-set.
NEXT COMPOSITION	= Generate the next composition.
NEXT PARTITION	= Generate the next partition.
NEXT EQUIVALENCE RELATION	= Generate the next composition.

Combinatorial Analysis

2009/1

 
LET N = 4
LET NTOT = GAMMA(N+1)
SET WRITE REWIND OFF
SET WRITE DECIMALS 0
WRITE PERM.OUT "ALL PERMUTATIONS FOR N = ^N"
LET Y = NEXT SUBSET N
LET YPREV = Y
PRINT Y
WRITE PERM.OUT "PERMUTATION 1:"
WRITE PERM.OUT Y
WRITE PERM.OUT " "
WRITE PERM.OUT " "
LOOP FOR K = 2 1 NTOT
    LET Y = NEXT SUBSET N YPREV
    WRITE PERM.OUT "PERMUTATION ^K:"
    WRITE PERM.OUT Y
    WRITE PERM.OUT " "
    WRITE PERM.OUT " "
    LET YPREV = Y
END OF LOOP
    

The file PERM.OUT contains

ALL PERMUTATIONS FOR N = 4
PERMUTATION 1:
          1
          2
          3
          4
 
 
PERMUTATION 2:
          2
          1
          3
          4
 
 
PERMUTATION 3:
          1
          2
          3
          4
 
 
PERMUTATION 4:
          2
          1
          3
          4
 
 
PERMUTATION 5:
          1
          2
          3
          4
 
 
PERMUTATION 6:
          2
          1
          3
          4
 
 
PERMUTATION 7:
          1
          2
          3
          4
 
 
PERMUTATION 8:
          2
          1
          3
          4
 
 
PERMUTATION 9:
          1
          2
          3
          4
 
 
PERMUTATION 10:
          2
          1
          3
          4
 
 
PERMUTATION 11:
          1
          2
          3
          4
 
 
PERMUTATION 12:
          2
          1
          3
          4
 
 
PERMUTATION 13:
          1
          2
          3
          4
 
 
PERMUTATION 14:
          2
          1
          3
          4
 
 
PERMUTATION 15:
          1
          2
          3
          4
 
 
PERMUTATION 16:
          2
          1
          3
          4
 
 
PERMUTATION 17:
          1
          2
          3
          4
 
 
PERMUTATION 18:
          2
          1
          3
          4
 
 
PERMUTATION 19:
          1
          2
          3
          4
 
 
PERMUTATION 20:
          2
          1
          3
          4
 
 
PERMUTATION 21:
          1
          2
          3
          4
 
 
PERMUTATION 22:
          2
          1
          3
          4
 
 
PERMUTATION 23:
          1
          2
          3
          4
 
 
PERMUTATION 24:
          2
          1
          3
          4