Dataplot Vol 2 Vol 1

# NEXT PERMUTATION

Name:
NEXT PERMUTATION (LET)
Type:
Let Subcommand
Purpose:
Generate the next permutation of n letters.
Description:
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.

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

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

Examples:
LET Y = NEXT PERMUTATION N
LET Y = NEXT PERMUTATION N YPREV
Note:
Dataplot implements this command using the algorithm NEXPER 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 permutation is the last permutation in the sequence for the given value of n. 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 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.
References: Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 7. Applications:
Combinatorial Analysis
Implementation Date:
2009/1
Program:
```
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
```

Date created: 1/21/2009
Last updated: 1/21/2009
Please email comments on this WWW page to alan.heckert@nist.gov.