## README

# historical-permutations

## A JavaScript library of historical permutation algorithms from 1956 to the present day.

I originally started collecting these algorithms together as I was doing some research on early permutation algorithms as part of an ongoing project about the "Permutation Poems" of the poet and artist Brion Gysin. However, I soon found that many of these algorithms were in hard-to-find papers and little documented, often because they were superseded by more efficient algorithms only years later.

I thought that this library might be of interest to those looking to learn about permutations or the history of early computing - especially those who are trying to find out more about the technology used to write early computational poetry.

Due to the focus of my own research, nearly all of these algorithms are from the period 1956-65.

I have tried to collect as many of the original papers as possible, and these now reside in the `papers`

folder of this repository - this addition does make this repo very large, however, these pdfs are only included in the git repository, and not in the package available on `npm`

.

Many of these algorithms are taken from Robert Sedgewick's 1977 paper *Permutation Generation Methods*.

Along with the algorithms themselves, now translated from ALGOL into JavaScript, there are a series of utilities, designed to make the use of the algorithms easier. These include a small program that allows the easy replacement of the elements within an array of permutations·

## Current Status

The current aim is to implement as many of the algorithms mentioned in the following section and release this as version 1.0.0. As of the end of April 2019, 18 of the 22 algorithms planned have been implemented and have been released on `npm`

as version 1.0.0.

- 8 March 2019 (v 0.1.0)
- Tompkins-Paige, Lehmer CDM, Hall, Coveyou-Sullivan, Wells, Peck-Schrack, Schrack-Shimrat, Heap, Myrvold-Ruskey

- 25 March 2019 (v 0.3.0)
- Superpermutation algorithm added.

- 26 March 2019 (v 0.4.0)
- Steinhaus-Johnson-Trotter added.

- 2 April 2019 (v 0.5.0)
- Gysin-Sommerville added.

- 9 April 2019 (v 0.6.0)
- Pandita added.

- 22 April 2019 (v 0.7.0)
- Langdon added.

- 24 April 2019 (v 0.8.0)
- Ord-Smith added.

- 24 April 2019 (v 1.0.0)
- Version 1.0.0 released.

## Permutation Algorithms Implemented

Ticks indicate the algorithm works and has been tested. Crosses indicate that algorithm is not and will not be included in the library and is only mentioned below for historical context. Information on all of these algorithms and their original implementations can be found below. I have focused only on including algorithms which give different orderings to each other when run, hence why I have only decided to implement one of the several lexicographic algorithms below.

Currently, the two algorithms lacking are Eaves, Boothroyd (BCJ30) and Ives.

- 1400 - Pandita [lexicographic] ✅
`pandita(4)`

- 1956 - Tompkins-Paige ✅
`tompkinsPaige(["one", 2, 3, "4"], 1)`

- 1960 - Lehmer [Constant Difference Method] ✅
`lehmer([1, 2, 3, 4])`

- 1960 - Walker Backtrack Method [lexicographic] ❌
- 1960 - D. N. Lehmer Lexicographic [lexicographic] ❌
- 1960 - Hall ✅
`hall(4)`

- 1961 - Coveyou-Sullivan (ACM71: PERMUTATION) ✅
`coveyouSullivan(4)`

- 1961 - Wells (ACM115) [Transposition Method] ✅
`wells(["1", 2, "3", 4])`

- 1962 - Peck-Schrack (ACM86: PERMUTE) [Tompkins-Paige w/ leftwise rotation] ✅
`peckSchrack(4)`

- 1962 - Schrack-Shimrat (ACM102: PERMULEX) [lexicographic] ✅
`schrackShimrat(4)`

- 1962 - Eaves (ACM130: Permute)
**for release in 2.0.0** - 1962 - Howell (ACM87: PERMUTATION) [lexicographic] ❌
- 1962/63 - Shen (ACM202: PERLE) [lexicographic] ❌
- 1962/63 - Steinhaus-Trotter-Johnson (ACM115: PERM)
- original ✅
`steinhausJohnsonTrotter(4)`

- loopless ✅
`steinhausJohnsonTrotter(4, "loopless")`

- Even's speedup ✅
`steinhausJohnsonTrotter(4, "even")`

- original ✅
- 1963 - Heap ✅
`heap([1, 2, 3, 4])`

- 1964 - Sag (ACM242) [permutation with repetitions] ❌
- 1967 - Langdon ✅
`langdon(4)`

- 1967 - Phillips (BCJ28) [lexicographic] ❌
- 1967 - Boothroyd (BCJ29) [Wells] ❌
- 1967 - Boothroyd (BCJ30) [for
*n*>=5]**for release in 2.0.0** - 1967 - Ord-Smith (ACM308: perm) [pseudo-lexicographic] ❌
- 1968 - Ord-Smith (ACM323: BESTLEX) [reverse lexicographic] ✅
`ordSmithRevLex([1, 2, 3, 4])`

- 1976 - Ives
**for release in 2.0.0** - 2001 - Myrvold-Ruskey [remainder order] ✅
`myrvoldRuskey(4)`

- 2018 - Superpermutations ✅
`superpermutation(4)`

- 2019 - Pocknee-Gysin-Sommerville [8 different orderings] ✅
`gysinSommerville(4, 1, -1)`

**CURRENT PROGRESS: 18 / 22 Algorithms Complete**

### Types Of Algorithm:

**Lexicographic:** `pandita()`

, `schrackShimrat()`

**Tompkins-Paige:** `tompkinsPaige()`

, `peckSchrack()`

**Lehmer Constant Difference:** `lehmer()`

**Hall:** `hall()`

**Coveyou-Sullivan:** `coveyouSullivan()`

**Wells:** `wells()`

**Steinhaus-Johnson-Trotter:** `stenhausJohnsonTrotter()`

**Heap:** `heap()`

**Langdon:** `langdon()`

**Reverse Lexicographic:** `ordSmithRevLex()`

**Myrvold-Ruskey:** `myrvoldRuskey()`

**Superpermutations:** `superpermutation()`

**Pocknee-Gysin-Sommerville:** `gysinSommerville()`

## Utilities

`rotate([1, 2, 3], 1)`

`rotateArrays([[1, 2, 3], [1, 3, 2], [2, 1, 3]], 1)`

`replace([[1, 2, 3], [1, 3, 2], [2, 1, 3]], [1, 2, 3], ["A", "B", "C"], 1)`

`reverseArrays([[1, 2, 3], [1, 3, 2], [2, 1, 3]])`

`swap([1, 2, 3, 4, 5], 0, 3)`

`mutatedSwap([1, 2, 3, 4, 5], 0, 3)`

`reverseNonMutate([1, 2, 3, 4, 5])`

`compareArrays([[1, 2, 3, 4], [1, 3, 2, 4], [1, 2, 3, 4], [1, 3, 2, 4]])`

`cyclicModulo(-2, 5)`

`factorial(4)`

## Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes. See deployment for notes on how to deploy the project on a live system.

### Prerequisites

If you just want to use the library and are not bothered about contributing to the project or running the testing suite that accompanies it, then there are no prerequisites needed for running the library, as it does not need the use of any external libraries. If you are planning on running the testing suite you will need to be running `node.js`

and install the devDependencies mentioned in the `package.json`

file (these include `lodash`

, `chai`

and `mocha`

).

### Installing

The simplest way to use this library is to download or clone the folder from the github repository onto a folder on your hardrive containing the project you want to use it with, then require or import in the files, as mentioned below in the `Deployment`

section. If you are cloning from github

### With node.js

If you are running your JavaScript using `node.js`

, the easiest way to use this library is either to download it directly through the node package manager (npm) by using the commandline or terminal to navigate to the folder where you want to install the library and running:

```
npm i historical-permutations
```

## Testing

Tests are written in `chai`

and `mocha`

and can be run through `node.js`

using the following commands:

`npm test`

runs tests on all functions in the library, including utilities and ordering algorithms but excluding algorithms in the`work-in-progress`

folder.`npm run test:utils`

only runs tests for the utiliities`npm run test:algo`

only runs tests for the finished permutation algorithms, excluding utilities.`npm run test:wip`

only runs the tests in the`work-in-progress`

folder.

The tests are written to ensure that all of the algorithms are implemented correctly and produce all possible permutations without repetition when given an array of a certain length. Tests are only included in the github repository, not in the npm release. On github, these tests are run through `travis-ci`

.

## Contributions

Contributions to this library are welome and can be made using a pull request to the github repository. Permutation algorithms that are finished and fully tested are placed in the `algorithms`

folder and their tests in the `spec`

folder. Utilities are found in the `utils`

folder and their tests are also kept in the `spec`

folder. Algorithms currently in progress or which have either not been fully tested or are failing current tests are kept in the `work-in-progress`

folder, which has its own `spec`

folder for tests.

## Deployment

The library can be included in your project by including either of the following lines at the top of your javascript file (implementation depends on the version of JavaScript you are using):

```
const permutations = require('historical-permutations');
import permutations from 'historical-permutations';
```

This will require in or import all of the permutations in the library, which can then be used by invoking them via the variable assigned to the library:

```
permutations.tompkinsPaige([1,2,3,4], 1);
```

If you only want to use a single algorithm, this can be done by destructuring it from the library when you import or require it in:

```
const { tompkinsPaige } = require('historical-permutations');
tompkinsPaige([1,2,3,4], 1);
```

Some of these algorithms can work with an array containing any type, as their algorithm is based on the position of the object in the array, but others will only work with arrays of numbers, as they are dependent upon evaluating the value of each element, not just its position. See the **Usage** section at the bottom of each algorithm description for more information.

### Examples

Examples of usage can be found in the `examples`

folder.

## Built With

`node.js`

`mocha`

`chai`

`lodash`

`eslint`

`prettier`

`travis-ci`

## Author

- David Pocknee

## Links

- NPM: https://www.npmjs.com/package/historical-permutations
- github: https://github.com/dpocknee/historical-permutations

## License

MIT

## Acknowledgments

- Special mention should go to the insipring repository at https://github.com/nodash/steinhaus-johnson-trotter.

# The Algorithms

## General Notes

Most of the algorithms below are taken from journals and articles from the 1950s and 1960s, when ALGOL was the standard language used in journals such as the *Communications of the ACM* and *The Computer Journal*.

Additionally, unlike many languages today, it was common not to use zero-based numbering for array elements; meaning that arrays are numbered starting from 1, not from 0. This means that for several of the modern JavaScript implementations an initial dummy element is added to the beginning of the arrays before feeding them into the algorithm, which is then removed upon termination.

For those algorithms from Sedgewick's paper, `process`

is where each resultant permutation is output. Any filtering of results can happen here. In the JavaScript implementations, this is replaced by the callback function `cb()`

.

## Pandita Algorithm (1400s)

A lexicographic approach has been implemented as the function `pandita()`

, taken from the wikipedia article on permutations:

There are many ways to systematically generate all permutations of a given sequence. One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. It begins by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been rediscovered frequently.[44]

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

- Find the largest index
ksuch thata[k]<a[k + 1]. If no such index exists, the permutation is the last permutation.- Find the largest index
lgreater thanksuch thata[k]<a[l].- Swap the value of
a[k]with that ofa[l].- Reverse the sequence from
a[k + 1]up to and including the final elementa[n].

### Usage

```
pandita(4);
```

## Tompkins-Paige Algorithm (1956)

Below is the ALGOL pseudo-code for the Tompkins-Paige Algorithm, as published in Robert Sedgewick's 1977 paper "Permutation Generation Methods" (Algorithm 5 in that paper on page 150). This is probably the oldest published permutation algorithm implemented on a computer.

```
```*i=N*; **loop**: *c[i]*=1 **while** *i*>2: *i*:=*i*-1 **repeat**;
*process*;
**loop**:
*rotate(i)*
**if** *c[i]*<*i* **then** *c[i]*:=*c[i]*+1; *i*:=2;
*process*;
**else** *c[i]*:=1; *i*:=*i*+1
**endif**;
**while** *i*≤*N* **repeat**;

Sedgewick, Robert. "Permutation Generation Methods".
In: ACM Comput. Surv. 9.2 (1977), pp. 137-164.
issn : 0360-0300. doi : 10.1145/356689.356692.
url : http://doi.acm.org/10.1145/356689.356692.

NOTE: In the algorithm above, rotate() is a function that does a cyclic left-rotation of the first *i* elments of the array:

```
```*t*:=P[1]; *k*:=2;
**loop while** *k*≤*i*: P[*k*-1]:=P[*k*] **repeat**;
P[*i*]:=*t*;

In my implementation, an extra parameter can be used to define whether the rotation command rotates parts of the array left or right, resulting in different outputs - this is done by specifying either `1`

or `-1`

as the second parameter. Other numbers can be used, but results will vary in success depending on the length of the array.

### Usage

```
tompkinsPaige(["one", 2, 3, "4"], -1);
```

Use arrays containing: **anything**

## D.H. Lehmer Constant Difference Method (1960)

This algorithm was originally proposed in D.H. Lehmer's 1960 paper *Teaching Combinatorial Tricks To A Computer*. In the paper, only a verbal description of the method is given, and there appears to be no easily-accessible implementation of it in modern languages.

"We pass on to what may be called the Constant Difference Method. Given a permutation like

2 3 1 5 4 0 7 6 8

one can obtain immediately another one by increasing every mark by unity, replacing 9 by 0 rather than by 10; thus

3 4 2 6 5 1 8 0 7 9

In fact, we get in this way 10 permutations all with the same set o differences modulo 10 between consecutive marks, namely

1 8 4 9 6 7 2 5 2

One may take as representative of these 10 permutation whose first element is zero, namely

0 1 9 3 2 8 5 7 4 6.

Similarly the permutation

1 0 3 2 8 5 7 4 6

in which we have taken the marks modulo 9, is one of 9 represented by

0 8 2 1 7 4 6 3 5.

This continues on down to the case of only two marks 0 1. This suggests the following method exemplified by the case of n = 5. We begin with the permutation 0 1 2 3 4. Adding 1 1 1 1 1 modulo 5 five times to return to 0 1 2 3 4. We now subtract 1 1 1 1 and then add it back again, this time modulo 4, obtaining 0 1 2 3 0. Once more we add 1 1 1 1, this time modulo 5, obtaining 0 2 3 4 1. This is our next permutation and there are four others it represents. Continuing we come to 0 4 1 2 3 which, after giving 1 0 2 3 4, 2 1 3 4 0, 3 2 4 0 1, 4 3 0 1 2, 0 4 1 2 3 gives rise in turn to

0 3 0 1 2, 0 0 1 2 3, 0 0 0 1 2, 0 0 1 2 0, 0 0 2 3 1

and finally 0 1 3 4 2, our next permutation. The process finally returns to 0 1 2 3 4.

This process has been coded for the SWAC and for the 701. It is about as fast as the Walker method. If permutations with specified properties of the differences between consecutive marks are required the process is very much faster than any previous one. An example of such a property is the requirement of the differences themselves forming a permutation as in cable splicing and other management problems. The method lends itself to fractional precision representation. For n = 8, for example, one permutation can be made from its predecessor in 128 microseconds on the SWAC."

Lehmer, D.H. "Teaching combinatorial tricks to a computer". In: Proceedings of Symposium Applied Mathematics: Combinatorial Analysis. 5.6 (June 1962), Vol. 10. Providence, R.I.: American Mathematical Society, 1960, pp. 179-193

### Usage

```
lehmer([1, 2, 3, 4]);
```

Use arrays containing: **only numbers**

## Walker Backtrack Method (1960)

The Walker Backtrack method was first proposed by R. J. Walker in "An Enumerative Technique for a Class Of Combinatorial Problems".

"There are various ways in which a linear order can be imposed on the elements of

Aso as to reduce this formulation to the general one stated above.One way of constructing a set

Ais to build it up element by element. Suppose thata_{1}, ... ,a_{k-1}have been chosen. The given restrictions will then require thata_{k}; belong to some subsetS_{k}ofU. IfS_{k}is not empty ana_{k}, can be chosen and the building-up process continued; ifS_{k}, is empty one must back-track and change one of the previousa’s. To do this systematically we shall assume that the elements of U have been linearly ordered, and shall always choosea_{k}to be the least element ofS_{k}. IfS_{k}is empty we return toS_{k-1}and changea_{k-1}to the next larger element ofS_{k-1}; if this is impossible we back-track still further. The following condensed program contains the essential features of this process as it would be done by an automatic calculator. It is to be assumed that Steps+ 1 will follow Stepsunless otherwise specified.General program.

- Set
k= 1.- Set
S_{k}=S_{1}.- If
S_{k}is empty jump to 9.- Set
a_{k}equal to the smallest element ofS_{k}.- If
k=njump to 14.- Replace
kbyk+ 1.- Compute
S_{k}.- Jump to 3.
- If
k= 1, stop.- Replace
kbyk— 1.- Compute
S_{k}.- Replace
S_{k}byS_{k}∩ {a|a>a_{k}}.- Jump to 3.
- Record
A= {a_{1}, ... ,a_{n}}.- Jump to 12.
This program is set up to record all possible sets

A. If, for example, they are merely to be counted, Step 14 may be modified accordingly. Other modifications might involve the use of other criteria than a fixed value of n for determining when a setAis completed (Step 5), or other criteria for stopping the process (Step 9).Walker, R. J. "An Enumerative Technique for a Class Of Combinatorial Problems". In: Proceedings of Symposium Applied Mathematics: Combinatorial Analysis. 5.6 (June 1962), Vol. 10. Providence, R.I.: American Mathematical Society, 1960, pp. 179-193

although the following is not a permutation algorithm but *the basis of a technique* which could be used for solving combinatorial problems, it is included here as Lehmer states that it was used for generating permutations and gives a verbal description:

The Walker Backtrack Method, given elsewhere in this volume in more general form, is described by him as “‘completely unsophisticated.” One regards a permutation of the marks 0, 1, 2, ... ,(

n— 1) as simply a vector whose components are taken from the non-negative integers <nbut are all distinct. One proceeds to construct such vectors starting from 0, 0, 0, 0, ... , 0, 0 filling in at each opportunity the least available mark. When a permutation is completed the last two marks are removed and the penultimate address is filled by the next largest mark available. If there is no next largest element available one more mark is removed and replaced by the next larger available mark, etc. The result is a complete set of permutations in lexicographical order. This process was coded by Walker, for a generaln, for the SWAC using only twenty-two commands. The program is slower than the Tompkins routine by a factor of two. I believe it could be altered to give random permutation and to skip over blocks of unwanted permutations. A similar program was devised by the writer to meet requirement (d) in 1955. Such programs are difficult to describe except in very general terms. In brief the machine keeps a sort of registry which shows at a glance which marks have been assigned to the permutation under construction and thereby avoids placing two marks in the same place and provides an automatic waiting list of marks as yet unassigned.Lehmer, D.H. "Teaching combinatorial tricks to a computer". In: Proceedings of Symposium Applied Mathematics: Combinatorial Analysis. 5.6 (June 1962), Vol. 10. Providence, R.I.: American Mathematical Society, 1960, pp. 179-193

## D. N. Lehmer Lexicographic (1960)

A third way of setting up correspondence was, in effect, suggested by D. N. Lehmer as long ago as 1906. It may be called the lexicographic method since it generates permutations in this order.

If in any permutation

a_{1},a_{2}, ...,a_{n}of the numbers 0(1)

n— 1 we strike out a; and reduce by unity all the marks which exceeda_{1}, we get a new permutationα

_{1}, α_{2}, ..., α_{n-1}of the numbers 0(1)

n— 2, which we may denote by

M(a_{1},a_{2}, ...,a_{n}).If we now define a rank function >

R(a_{1},a_{2}, ...,a_{n}) recursively by

R(0) = 0,R(>

M(a_{1},a_{2}, ...,a_{n}).) =a_{1}(n— 1)! +R(M(a_{1},a_{2}, ...,a_{n}))it is seen that

Ris nothing but the rank or serial number of the permutation (a_{1},a_{3}, ...,a_{n}) in the lexicographical list of all permutations. In fact, in this list the first (n— 1)! permutations have 0 as their first mark, the next (n— 1)! permutations have 1 as their first mark, and so on. Since our permutation has a, as its first mark it is preceded bya_{1}(n— 1)! permutations whose first mark is less thana_{1}. Among those permutations which begin witha_{1}, ours has rankR(M(a_{1},a_{2}, ...,a_{n})). If one successively applies the operation M we get a sequence of » — 1 permutations whose first elements are the factorial digits of the rank of the original permutation. Thus for example, for n = 7, the permutation 1 4 2 0 5 6 3 gives rise to

```
1 4 2 0 5 6 3
3 1 0 4 5 2
1 0 3 4 2
0 2 3 1
1 2 0
1 0
0
```

Hence the rank of 1 4 2 0 5 6 3 is

1, 3, 1, 0, 1, 1 = 6! + 3-5! + 4! 4+ 2! 4 1! = 1107.

Conversely given the rank and its factorial digits

S_{n—1}, S_{n-2}, ..., S_{2}, S_{1}we may reconstruct the permutation having this rank. Beginning with 0 we affix S

_{1}and in case S_{1}is 0, we increase the original 0 to 1. Thus we getO 1 if S

_{1}= 0,1 0 if S

_{1}= 1.

## Hall (1960) [Method of Derangements]

"We turn now to a second way of making a permutation correspond to its factorial digits. This method was suggested by Marshall Hall and may be called the Method of Derangements. In the previous method the objects being permuted can be any computer words. In the Hall method the objects must be the numbers 0(1)

n— 1. In any such permutation we may, for each markk> 0, ask how many of thekmarks less than k actually follow k. Denoting this number by Sx we see at once that

S_{n-1},S_{n-2}, ...S_{2},S_{1}is a set of factorial digits of a number which corresponds to the given permutation and which, conversely, characterizes this permutation. We have for example the following correspondencies when n = 7.

S_{6}S_{5}S_{4}S_{3}S_{2}S_{1}0 0 0 0 0 0 0 1 2 3 4 5 6 3 1 4 1 2 1 4 2 1 6 3 5 0 1 2 2 3 1 1 3 1 4 5 2 6 0 6 5 4 3 2 1 6 5 4 3 2 1 0 The coding of this method is fairly straightforward. The resulting routine is a good deal slower than the Tompkins-Paige method. The parities of successive permutations strictly alternate. The method is well suited to requirement (c) [in the paper]."

Lehmer, D.H. "Teaching combinatorial tricks to a computer". In: Proceedings of Symposium Applied Mathematics: Combinatorial Analysis. 5.6 (June 1962), Vol. 10. Providence, R.I.: American Mathematical Society, 1960, pp. 179-193

### Usage

`hall(4)`

will generate all possible permutations of the array `[1, 2, 3, 4]`

.

## Coveyou-Sullivan (1961) [Algorithm ACM71]

This algorithm, named `PERMUTATION`

, was originally published by R. R. Coveyou and J. G. Sullivan in the November 1961 issue of *Communications of the ACM* as algorithm ACM71.

```
```**procedure** PERMUTATION (I, P, N);
**value** I, N; **integer** N; **integer array** P; **boolean** I;
**comment** This **procedure** produces all permutations of the integers from 0 through N.
Upon entry with I = **false** the **procedure** initializes itself producing no permutation.
Upon each successive entry into the **procedure** with I = **true**
a new permutation is stored in P[0] through P[N].
When the process has been exhausted a sentinel is set:
P[0]: -1,
N ≥ 0;
**begin**
**integer** i; **own integer array** x[0:N];
**if** ¬ I **then**
**begin for** i := 0 **step** 1 **until** N-1 **do** x[i] := 0; x[N] := -1;
**go to** E **end**;
**for** i := N **step** -1 **until** 0 **do begin if** x[i]≠i **then go to** A;
i := 0 **end**;
P[0] := -1; **go to** E;
A: x[i] := x[i]+1; P[0] := 0;
**for** i:= 1 **step** 1 **until** N **do**
**begin** P[i] := P[i-x[i]]; P[i-x[i]] := i **end**
E: **end** PERMUTATION

Coveyou, R. R. and J. G. Sullivan. "Algorithm 71: permutation".
In: Communications of the ACM 4.11
(Nov. 1961), p. 497.

## Usage

`coveyouSullivan(4)`

will generate all possible permutations of the array `[1, 2, 3, 4]`

.

## Wells (1961)

This algorithm, by M. B. Wells, was originally described in the 15th issue of the journal *Mathematics of Computation* in the article "Generation of permutations by transposition". This implementation is based Boothroyd's 1965 improvement, and taken from Sedgewick's paper:

```
```**procedure** *permutations*(*N*)
**begin** *c*:=1;
**loop**:
**if** *N*>2 **then** *permutations*(*N*-1)
**endif**;
**while** *c*<N;
P[B[*N*,*c*]]:=:P[*N*];
*c*:=*c*+1
**repeat**
**end**;

in which `P[B[N,c]]:=:P[N];`

is:

```
```**if** (N *even*) and (*c*>2)
**then** P[*N*]:=:P[*N*-*c*]
**else** P[*N*]:=:P[*N*-1] **endif**

Wells, M. B. "Generation of permutations by transposition". In: *Mathematics of Computation* 15 (1961) pp. 192-195.

NOTE: Because of the fact the original algorithm is based on an array in which the indexes start from 1 rather than 0, and that it will not work otherwise, the algorithm inserts a meaningless placeholder element in the first position (e.g. the '0' in [0,1,2,3,4,5]), then removes it for the output.'. This algorithm also only takes in

```
wells(["1", 2, "3", 4]);
```

Use arrays containing: **anything**

## Peck-Schrack (1962)

This algorithm was implemented in `ALGOL`

by Peck and Schrack in 1962. It gives the same result as the Tompkins-Paige algorithm with a left-wards rotation. i.e. in this library `peckSchrack(4)`

gives the same result as `tompkinsPaige([1, 2, 3, 4], 1)`

but not `tompkinsPaige([1, 2, 3, 4], -1)`

.

```
```**procedure** PERMUTE (x,n);
**array** x; **integer** n;
**comment** Each call of PERMUTE executes a permutation of the first n components of x.
It assumes a nonlocal Boolean variable 'first',
which when true causes the procedure to initialise the signature vector p.
Thereafter 'first' remains false until after n! calls;
**begin own integer array** p[2:n]; **integer** i k;
**if** first **then**
**begin for** i := 2 **step** 1 **until** n **do**
p[i] := i; first := **false**
**end** initialise;
**for** k := 2 **step** 1 **until** n **do**
**begin integer** km; **real** t;
t := x[1]; km := k - 1;
**for** i := 1 **step** 1 **until** km **do**
x[i] := x[i+1];
x[k] := t; p[k] := p[k] - 1;
**if** p[k] ≠ 0 **then go to** EXIT;
p[k] := k
**end** k;
first := **true**;
EXIT: **end** PERMUTE

Peck, J. E. L. and G. F. Schrack. "Algorithm 86: Permute".
In: Communications of the ACM 5.4 (Apr. 1962), pp. 208-209

## Usage

`peckSchrack(4)`

will generate all possible permutations of the array `[1, 2, 3, 4]`

.

## Howell (1962) [ACM87: PERMUTATION]

```
```**procedure** PERMUTATION (N, K);
**value** K, N; **integer** K; **integer array** N;
**comment** This procedure generates the next permutation in
lexicographic order from a given permutation of the *K* marks
0, 1, ..., (K-1) by the repeated addition of (K—1) radix K.
The radix K arithmetic is simulated by the addition of 9 radix
1O and a test to determine if the sum consists of only the original
K digits. Before each entry into the **procedure** the K marks
are assumed to have been previously specified either by input
data or as the result of a previous entry. Upon each such entry a
new permutation is stored in N[1] through N[K]. In case the
given permutation Is (K—1), (K—2), ... , 1, 0, then the next
permutation is taken to be 0, 1, ..., (K — 1). A FORTRAN
subroutine for the IBM 7090 has been written and tested for
several examples;
**begin integer** i, j, carry;
**for** := 1 **step** 1 **until** K **do**
**if** N[i] — K + i ≠ 0 **then go to** add;
**for** i := 1 **step** 1 **until** K **do** N[i] := i — 1;
**go to** exit;
add: N[K] := N[K] + 9;
**for** i := 1 **step** 1 **until** K—1 **do**
**begin if** K > 10 **then go to** B;
carry := N[K-i+1]÷10; **go to** C;
B: carry := N[K-i+1]÷K;
C: **if** carry = 0 **then go to** test;
N[K-i] := N[K—i] + carry;
N[K—i+1] := N[K—i+1] —10 × carry
**end** i;
test: **for** i := 1 **step** 1 **until** K **do if** N[i]- (K-1) > 0
**then go to** add;
**for** i := 1 **step** 1 **until** K-1 **do**
**for** j := i+1 **step** 1 **until** K **do**
**if** N[i]-N[j] = 0 **then go to** add;
exit: **end** PERMUTATION GENERATOR

Howell, John R. "Algorithm 87: Permutation generator". In:
Communications of the ACM 5.4 (Apr. 1962), p. 209.

## Schrack-Shimrat (1962) [ACM102: PERMULEX lexicographic]

The algorithm below is also known as the *Fischer-Krause* algorithm, and has been known since 1812. This is how it is presented in Sedgewick's paper:

```
P[
```*N* + 1] = ∞;
*process*;
**loop**.
*i*:=2; **loop while** P[*i*] < P[*i*-1]; *i*:=*i*+1 **repeat**;
**while** *i*<*N*;
*j*:=1; **loop while** P[*j*]>P[*i*]; *j*:=*j*+1 **repeat**;
P[*i*]:=:P[*j*]
*reverse*(*i*-1);
*process;*
**repeat**;

where `reverse()`

"inverts the order of the elements in `P[1],....,P[i]`

:

```
```*i*:=1;
**loop while** *i*<*N*+1-*i*;
P[*i*]:=:P[*N*+1-*i*]; *i*:=*i*+1 **repeat**;

Schrack and Shimrat later implemented this code as ACM Algorithm 102:

```
```**procedure** PERMULEX(n,p);
**integer** n; **integer array** p;
**comment** Successive calls of the procedure will generate all
permutations p of 1,2,3,---,n in lexicographical order. Before the
first call, the non-local Boolean variable ‘flag’ must be set to
**true**. If after an execution of PERMULEX ‘flag’ is **false**,
additional calls will generate further permutations—if true, all
permutations have been obtained ;
**begin integer array** q[1:n]; **integer** i, k, t; **Boolean** flag2;
**if** flag **then**
**begin for** i := 1 **step** 1 **until** n **do**
p[i] := i; flag2 := **true**; flag := **false**;
**go to** EXIT
**end** initialize;
**if** flag2 **then**
**begin** t := p[n]; p[n] := p[n—1]; p[n—1] := t;
flag2 := **false**; **go to** EXIT
**end** bypass;
flag2 := **true**; **for** i := n—2 **step** —1 **until** 1 **do**
**if** p[i] < p[i+1] **then go to** A;
flag := **true**; **go to** EXIT;
A: **for** k := 1 **step** 1 **until** n **do** q[k] := 0;
**for** k := 1 **step** 1 **until** n **do** q[p[k]] := p[k];
**for** k := p[i] + 1 **step** 1 **until** n **do**
**if** q[k] ≠ 0 **then go to** B;
B: p[i] := k; q[k] := 0;
**for** k := 1 **step** 1 **until** n **do**
if q[k] ≠ 0 **then begin** i := i + 1; p[i] := q[k] **end**
**else if** i ≥ n **then go to** EXIT;
EXIT:
**end** PERMULEX

G. F. Schrack and M. Shimrat. "Algorithm 102: Permutation in lexicographical order".
In: Communications of the ACM 5.6 (June 1962), p. 346.

### Usage

```
schrackShimrat(4);
```

Use arrays containing: **only numbers**

## Eaves (1962) [ACM130: Permute]

```
```**procedure** PERMUTE (A, n, x)
**array** *A*; **integer** *n*, *x*;
**comment** Each entry into *PERMUTE* generates the next per-
mutation of the first n elements of A. If A is read as a number
(*A*[1]*A*[2] ... *A*[n]), each generation is larger than the last:
*n* := 4, *x* := 1
*A*[l] 1 1 1 8 8 8
*A*[2] 1 8 8 1 1 8
*A*[3] 8 1 8 1 8 1
*A*[4] 8 8 1 8 1 1 end
Permutations = 4!/2!2!
Identical elements in *A* reduce the number of permutations. The
array should be ordered before the first call on PERMUTE.
Integer x specifies the first elements whose order should be pre-
served: *n* := 4, *x* := 3
*A*[1] 1 1 1 4
*A*[2] 2 2 4 1
*A*[3] 3 4 2 2
*A*[4] 4 3 3 3 end
Permutations = 4!/3!
Before the first call on PERMUTE for a given array, first
should be made true. If more is true, then PERMUTE was able
to give another permutation;
**begin array** B[1:*n*]; **integer** *f,i,k,m,p*; **real** *r*; **own real** *t*;
**if** *first* **then** *t* := *A*[*x*]; *first* := **false**;
**for** *i* := 1 **step** 1 **until** *n* **do** *B*[*i*] := 0;
**for** *i* := *n* **step** —1 **until** 2 **do**
**begin if** *A*[*i*] > t∧*A*[*i*] > *A*[*i* — 1] **then go to** *find*; **end**;
*more* := **false**; **go to** *exit*;
*find*: **for** *k* := *n* **step** —1 **until** *i* **do**
**begin if** *A*[*k*] > *t*∧*A*[*k*] > *A*[*i*—1] **then**
**begin** *B*[*k*] := *A*[*k*]; *m* := *k*; **end**; **end**;
**for** *k* := *n* **step** —1 **until** *i* **do**
**begin if** *B*[*k*] > 0 *A*∧*B*[*k*] < *B*[*m*] **then**
**begin** *B*[*m*] := *B*[*k*]; *f* := *k*; **end**; **end**;
*r* := *A*[*i*—1]; *A*[*i*—1]:= *B*[*m*]; *A*[*f*]] := *r*;
*schell*: *p* := *i*—1; *m* := *n* — *p*;
**for** *m* := *m*/2 — *A* **while** *m* > 0 **do**
**begin** *k* := *n* — *m*;
**for** *f* := *p* + 1 **step** 1 **until** *k* **do**
**begin** *i* := *f*;
*comp*: **if** *A*[*i*] > *A*[*i* + *m*] **then**
**begin** *r* := *A*[*i* + *m*]; *A*[*i* + *m*] := *A*[*i*];
*A*[*i*] := *r*; *i* := *i* — *m*;
**if** *i* ≥ *p* + 1 **then go to** *comp*;
**end end end** *schell*;
*exit*: **end** *PERMUTE*

Eaves, B. C. "Algorithm 130: Permute". In:
Communications of the ACM 5.11 (Nov. 1962), p. 551.

## Shen (1962/63) [lexicographic order]

Mok-Kong Shen's method of enumerating permutations in lexicographic order was first proposed in their 1962 paper *On the Generation of Permutations and Combinations* and later formalized in the September 1963 issue of *Communications of the ACM*, in the form of Algorithm 202: PERLE:

```
```**procedure** *PERLE* (*S*, *N*, *I*, *E*)
**integer array** *S*; **integer** *N*; **Boolean** *I*; **label** *E*;
**comment** If the array *S* contains a certain permutation of the
*N* digits *1, 2,..., N* before call, the procedure will replace
this with the lexicographically next permutation. If initializa-
tion is required set the Boolean variable *I* equal **true**, which
will be changed automatically to **false** through the first call,
otherwise set *I* equal **false**. If no further permutation can be
generated, exit will be made to *E*. For reference see *BIT 2* (1962) , 228-231;
**begin integer** *j, u, w*;
**if** *I* **then begin for** *j* = 1 **step** 1 **until** *N* **do** *S*[*j*] := *j*;
*I* := **false**; **go to** *Rose*
**end**;
*w* := *N*;
*Lilie*: **if** *S*[*w*] < *S*[*w*—1] **then**
**begin if** *w* = 2 **then go to** *E*;
*w* := *w* — 1; **go to** Lilie
**end**;
*u* := *S*[*w*—1];
**for** *j* := *N* **step** —1 **until** *w* **do**
**begin if** *S*[*j*] > *u* **then**
**begin** *S*[*w*—1] := *S*[*j*];
*S*[*j*] := *u*; **go to** *Tulpe*
**end**
**end**;
*Tulpe*: **for** *j* := 0 **step** 1 **until** (*N*—*w*—1)/2 + 0.1 **do**
**begin** *u* := *S*[*N*—*j*];
*S*[*N—j*] := *S*[*w*+*j*]; *S*[*w*+*j*] := *u*
**end**;
*Rose*:
**end** *PERLE*

## Steinhaus-Trotter-Johnson (1962/63) [ACM115: PERM]

This technique was "discovered" almost simultaneously by Steinhaus, Johnson and Trotter, although it has actually been in use in English bell-ringing since at least the 18th Century. Sedgewick formulates it as:

```
```*i*:=1;
**loop while** *i*≤*N*; *i*:=*i*+1; *c[i]*:=1;
*d[i]*:= **true**; **repeat**;
*c[1]*:=0;
*process*;
**loop**:
*i*:=*N*; *x*:=0;
**loop while** *c[i]*=*i*;
**if not** *d[i]* **then** *x*:=*x*+1 **endif**;
*d[i]*:=**not** *d[i]*; *c[i]*:=1; *i*= *i*-1;
**repeat**;
**while** *i*>1;
**if** *d[i]* **then** *k*:=*c[i]*+*x*
**else** *k*:=*i*-*c[i]*+*x* **endif**;
P[*k*]:=:P[*k*+1];
*process*;
*c[i]*:=:*c[i]*+1;
**repeat**;

Trotter's version of this algorithm was published as PERM: ACM Algorithm 115, in 1962:

`Trotter, H. F. "Algorithm 115: Perm". In:`

procedurePERM(x,n);valuen;integern;arrayx;commentThis algorithm was inspired by the procedure PERMUTE of Peck and Schrack (Algorithm 86,Comm. ACMApr. 1962) and performs the same function. Each call of PERM changes the order of the first » components of z, and n! succes- sive calls will generate all n! permutations. A nonlocal Boolean variable ‘first’? is assumed, which must be true when PERM is first called, to cause proper initialization. The first call of PERM makes ‘first’?false, and it remains so (unless changed by the external program) until the exit from the (n!)th call of PERM. At that time z is restored to its original order and ‘first’ is madetrue. The excuse for adding PERM to the growing pile of permuta- tion generators is that, at the expense of some extraownstorage, it cuts the manipulation of z to the theoretical minimum of n! transpositions, and appears to offer an advantage in speed. It also has the (probably useless) property that the permutations it generates are alternately odd and even;begin own integer arrayp, d[2:n];integerk,q;realt;iffirsttheninitialize:begin fork:= 2step1untilndobeginp[k] := 0;d[k] := 1end;first:=falseendinitialize;k:= 0;INDEX:p[n] :=q:=p[n] +d[n];ifq=nthenbegind[n] := —1;go toLOOPend;ifq ≠ Othen go toTRANSPOSE;d[n] := 1;k:=k+ 1;LOOP:ifn> 2then begincommentNote thatnwas called by value;n:=n— 1;go toINDEXendLOOP;Final exit:q:= 1;first:=true;TRANSPOSE:q:=q+k;t:=x[q];x[q] :=x[q+ 1]; :=tendPERM;Communications of the ACM5.8 (Aug. 1962), pp. 434-435.

This algorithm can also be implemented as a **loopless** algorithm, which gives the same result but runs slightly slower. It is described by Sedgewick as:

```
```*i*:=0;
**loop while** *i*≤*N*; *i*:=*i*+1; *c[i]*:=1; *d[i]*:= **true**;
*s[i]*:= *i*-1; *x*[*i*]:=0 **repeat**;
*process*;
**loop**:
*s*[*N*+1]:=*N*; *x*[*i*]:=0;
**if** *c*[*i*] = *i* **then**
**if not** *d[i]*
**then** *x*[*s*[*i*]]:=*x*[*s*[*i*]]+1; **endif**;
*d[i]*:=**not** *d[i]*; *c[i]*:=1;
*s*[*i*+1]:= *s*[*i*]; *s*[*i*]:=*i*-1;
**endif**;
*i*:=*s*[*N*+1];
**while** *i*>1;
**if** *d[i]* **then** *k*:=*c[i]*+*x*[*i*]
**else** *k*:=*i*-*c[i]*+*x*[*i*] **endif**;
P[*k*]:=:P[*k*+1];
*process*;
*c[i]*:=:*c[i]*+1;
**repeat**;

A slightly different ordering can be found using a version popularised by Shimon Even in his 1973 book **Algorithmic Combinatorics**, commonly referred to as **Even's Speedup**. This results in a different ordering, in which the highest, rather than lowest number zig-zags across the permutations. This works by assigning each mark a direction of left or right. All marks start with a left-wards direction.

Let us denote by an arrow above each integer its

direction, namely, the direction in which it tends to o. We start with all the directions pointing from right to left. Thus, ifn= 4, our initial data are as follows:`< < < < 1 2 3 4`

An integer

kismobileif there exists an integer smaller thankadjacent tokon the side where the direction ofkpoints to. For our example, in our initial position described above, the integers 2, 3, and 4 are mobile. In the case`< > < < 2 3 4 1`

only 4 is mobile.

Algorithm 1.1

- (1) If there are no mobile integers, stop.
- (2) Call the largest mobile integer
m.- (3) Let
mswitch places with the adjacent integer to which _m_th direction points to.- (4) Switch the direction of all integers _k* for which _k* >
m. Return to step (1).Let us demonstrate the algorithm for

n= 4:`< < < < 1 2 3 4 < < < < 1 2 4 3 < < < < 1 4 2 3 < < < < 4 1 2 3 > < < < 4 1 3 2 < > < < 1 4 3 2 < < > < 1 3 4 2 < < < > 1 3 2 4 < < < < 3 1 2 4 < < < < 3 1 4 2 ...`

- Shimon Even

Algorithmic Combinatorics(1973), Macmillan, New York, pp. 2-3.

### Usage

The **loopless** and **Even's Speedup** algorithms can be used by passing in a second argument into the function:

```
steinhausJohnsonTrotter(4)
steinhausJohnsonTrotter(4, "loopless")
steinhausJohnsonTrotter(4, "even")
```

## Heap (1963)

The following implementation comes from Sedgewick's paper:

```
```*i*:=*N*; **loop**: *c*[*i*]:=1 **while** *i*>2: *i*:=*i*-1 **repeat**;
*process*;
**loop**
**if** *c*[*i*]<*i*
**then if** *i odd* **then** *k* := 1 **else** *k*:=*c*[*i*] **endif**;
P[*i*]:=:P[*k*];
*c*[*i*]:=*c*[*i*] + 1; *i*:=2;
*process*,
**else** *c*[*i*]:=1; *i*:=+1
**endif**;
**while** *i*≤*N* **repeat**;

### Usage

```
heap([1, 2, 3, 4]);
```

## Langdon (1967)

The following version of Langdon's algorithm is partly taken from Sedgewick's paper, although his version mixes up the conditions in the first `IF`

statement and misses out a piece of conditional logic that prevents duplicates. My implementation is:

```
```*i* := 1; **loop**: P[*i*]:=Q[i] **while** *i*<N *i*:=*i*+1 **repeat**,
*process*;
**loop**:
*rotate(i)*;
**if** P[*i*] = *i* **then** *i*:=*i*-1 **else** *i*:=*N* **endif** ;
**if** P ≠ Q **and** *i* = n **then** *process*; **endif** ;
**while** *i*≥1 **repeat**;

### Usage

```
langdon(4);
```

## Boothroyd (1967) [BCJ30]

## Ord-Smith (1968) [ACM308][pseudo-lexicographic]

`R. J. Ord-Smith "Generation of permutation sequences: Part 1",`

procedureperm(x,n);valuen;integern;arrayx;begin own integer arrayq[3:10];integerk, m;realt;own booleanodd;iffirstthen beginodd:=true;ifn> 2then beginfirst:=false;form:= 3step1until2doq[m] := 1endendifoddthen beginodd:=false;t:=x[1];x[1] :=x[2];x[2] :=t;gotofinishend;odd:=true;k:= 3;oop:m:=q[k];ifm=kthenbegin ifk<nthen beginq[k] := 1;k:=k+ 1;gotoloopendelse beginfirst:=true;gototrinitendend;q[k] :=m+ 1;trinit:m:= 1;transpose:t=x[m];x[m] :=x[k];x[k] :=t;m:=m+ 1;k:=k— 1;ifm<kthen gototranspose;finish:endof procedure perm;The Computer Journal, (1970), 13.2, pp. 152-155

Ord-Smith's pseudo-lexicographic algorithm can be seen above, but as was proved in the 1991 paper "Ord-Smith's pseudo-lexicographical permuta-tion procedure is the Tompkins-Paige algorithm" in *The Computer Journal* - this algorithm gives out the same result as reversing the rotation direction in the Tompkins-Paige algorithm, so has not been implemented.

## Ord-Smith (1968) [ACM323][reverse lexicographic]

### Usage

```
ordSmithRevLex([1, 2, 3, 4])
```

## Ives (1976)

This is an alternate implementation of Ives' algorithm, given in Sedgewick's paper:

```
```*i*=*N*; **loop**: *c*[*i*]:=1; **while** *i*>1: *i*:=*i*-1 **repeat**
*process*;
**loop**
**if** *c*[*i*]<*N*+1-*i*
**then if** *odd* **then** P[*c*[*i*]]:=:P[*c*[*i*]+1]
**else** P[*i*]:=:P[*N*+1-*i*] **endif**,
*c*[*i*]:=*c*[*i*]+1, *i*=1;
*process*
**else** *c*[*i*]:=1; *i*=*i*+1;
**endif**
**while** *i*≤*N* **repeat**;

## Myrvold and Ruskey (2001) [remainder order]

The following algorithm lies much outside the original timescale I set for the project but has been included as it is a useful way of selecting individual permutations by rank and the algorithm itself is novel.

"The second order, which we call remainder order, was used by Myrvold and Ruskey [15]. Informally, let ( x , y ) denote the swap of the xth and yth symbol of a string. For example, applying ( 4 , 2 ) to 456123 gives 416523. Swaps are also called transpositions. In remainder order, the ith permutation is obtained from the identity permutation by a series of

n− 1 transpositions. The first indices of the transpositions aren,n− 1 , ... , 2. The second indices are remainders wheniis successively divided byn,n− 1 , ... , 2, plus one. For example, here are the calculations fori= 92 andn= 5

92 ÷ 5 = 18 18 ÷ 4 = 4 4 ÷ 3 = 1 1 ÷ 2 = 0 remainder 2 remainder 2 remainder 1 remainder 1 . In this calculation, each successive quotient is used in the next division, and the divisors are in turn 5, 4, 3, 2. The underlined remainders (plus one) imply that the 92nd permutation for n = 5 is obtained from 12345 by successively applying the following transpositions: ( 5 , 3 ), ( 4 , 3 ), ( 3 , 2 ), ( 2 , 2 ) . The resulting permutation is 14253... [the first object has rank 0]... Although this description is somewhat unorthodox, it directly translates into a simple unranking algorithm, which converts an integer

iinto the object of ranki. In remainder order, the unranking and ranking algorithms use O(n) arithmetic operations on values that can be as large asn!."Stephane Durocher, Pak Ching Li, Debajyoti Mondal, Frank Ruskey, Aaron Williams "Cool-lex order and k-ary Catalan structures",

Journal of Discrete Algorithms, Volume 16, 2012, Pages 287-307,

### Usage

```
myrvoldRuskey(4);
```

## Superpermutations (2018)

"A superpermutation[1] is a string formed from a set of n symbols such that every one of the n! permutations of those symbols appears exactly once as a contiguous block of n characters in the string." - Greg Egan

This is my own implementation of a superpermutation algorithm that should give string lengths equivalent to:

L(n) = 1! + 2! + ... +n!

This gives a result where:

*L*(2) = 3*L*(3) = 9*L*(4) = 33*L*(5) = 153*L*(6) = 873*L*(7) = 5913*L*(8) = 46,233*L*(9) = 409, 133

The algorithm takes a graph-based approach to creating small weight-1-cycle graphs (e.g. `[1, 2, 3, 4, 1, 2, 3]`

) that contain all possible permutations that can be created through rotation (i.e. `[1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 1, 2, 3]`

) that are then connected via reversing different-sized segments of each permutation.

More information on superpermutations can be found at Greg Egan's site

### Usage

```
superpermutation(4);
// -> [1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2, 1, 3, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1]
```

## Pocknee-Gysin-Sommerville (2019)

This is a unique collection of algorithms inspired by Brion Gysin and Ian Sommerville's pre-1965 *Permutation Poems*. Although many sources claim that these early poems were generated by computer, there seems to be little evidence to support this. Given the fact that none of these poems use permutation algorithms known at the time, the only other possibility is that they were either written by hand or used a unique algorithm designed by Ian Sommerville that is not found anywhere in the existing literature. I have attempted to create the type of algorithm that would have been needed to create these poems. Due to the large variety of orderings within these poems, this function contains 8 possible permutation options. These are examples of what I refer to as Gysin's "Magic Square"-esque approach to creating *Permutation Poems*. I want to stress that there is no evidence that Gysin or Sommerville actually used these algorithms and the implementation is my own creation.

The differnce between the 8 algorithms can be most easily seen by enumerating the permutations of n=3, seen below. The numbers in brackets above each set of permutations indicate the three arguments needed to be fed into the `gysinSommerville()`

function to get these results.:

`(3, 1, 1)` |
`(3, 2, 1)` |
`(3, 3, -1)` |
`(3, 4, 1)` |

1 2 3 | 1 2 3 | 1 2 3 | 1 2 3 |

2 3 1 | 2 3 1 | 2 1 3 | 2 1 3 |

3 1 2 | 3 2 1 | 3 1 2 | 3 2 1 |

1 3 2 | 1 3 2 | 1 3 2 | 1 3 2 |

2 1 3 | 2 1 3 | 2 3 1 | 2 3 1 |

3 2 1 | 3 1 2 | 3 1 2 | 3 1 2 |

`(3, 1, -1)` |
`(3, 1, -1)` |
`(3, 3, 1)` |
`(3, 4, -1)` |

1 2 3 | 1 2 3 | 1 2 3 | 1 2 3 |

3 1 2 | 3 1 2 | 2 1 3 | 3 2 1 |

2 3 1 | 2 1 3 | 2 3 1 | 2 1 3 |

1 3 2 | 1 3 2 | 3 2 1 | 1 3 2 |

3 2 1 | 3 2 1 | 3 1 2 | 3 1 2 |

2 1 3 | 2 3 1 | 1 3 2 | 2 3 1 |

### Usage

The three arguments in this function are: `length of array`

, `type of algorithm (1, 2, 3 or 4)`

, `direction of rotation (1 or -1)`

. There are four possible algorithms to choose from and each one can run using either a leftwise or rightwise rotation.

As an example, to create all permutations for n=4, using algorithm #3 with leftwise rotation, you would type:

```
gysinSommerville(4, 3, -1)
```

# The Utilities

This is a series of utilities that are useful for manipulating the output of the permutation algorithms.

## rotate()

This rotates an array either left or right by a given number of elements. The direction of the rotation depends upon whether the second argument is more than or less than 0.

```
rotate([1, 2, 3], 0);
// -> [1, 2, 3]
rotate([1, 2, 3], 1);
// -> [2, 3, 1]
rotate([1, 2, 3], 2);
// -> [3, 1, 2]
rotate([1, 2, 3], 3);
// -> [1, 2, 3]
rotate([1, 2, 3], -1);
// -> [3, 1, 2]
rotate([1, 2, 3], -2);
// -> [2, 3, 1]
rotate([1, 2, 3], -3);
// -> [1, 2, 3]
```

## rotateArrays()

Applies the above `rotate()`

function to every array within an array.

```
const testArray = [[1, 2, 3], [1, 3, 2], [2, 1, 3]];
rotateArrays(testArray, 1);
// -> [[2, 3, 1], [3, 2, 1], [1, 3, 2]];
rotateArrays(testArray, -2);
// -> [[2, 3, 1], [3, 2, 1], [1, 3, 2]]
```

## reverseArrays()

Reverses every array within an array.

```
reverseArrays([[1, 2, 3], [1, 3, 2], [2, 1, 3]]);
// -> [[3, 2, 1], [2, 3, 1], [3, 1, 2]];
```

## swap()

Swaps the position of two elements within an array. First argument is the array this function to be applied to and the following two arguments are the indexes of the two arrays to swap. This is function does not mutate the original array, but returns a new shallow copy.

```
swap([1, 2, 3, 4, 5], 0, 3);
// -> [4, 2, 3, 1, 5];
```

## mutatedSwap

Swaps the position of two elements within an array. First argument is the array this function to be applied to and the following two arguments are the indexes of the two arrays to swap. This is function **does** mutate the original array and is used in the Heap and Wells permutations.

```
mutatedSwap([1, 2, 3, 4, 5], 0, 3);
// -> [4, 2, 3, 1, 5];
```

## replace()

Replaces all of the elements in an array of arrays with different elements. This is useful as many of the algorithms can only return permutations of sequential numbers and this allows the transformation of these arrays such that they can contain other elements.

The first argument is the array of permutaions to transform, the second is the elements contained in the original permutation, the third is an array of elements to replace those in argument 2 with and the last is either `0`

/`false`

or `1`

/`true`

indicating whether the output should contain the original array as well as the transformed version.

```
const testArray = [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]];
replace(testArray, [1, 2, 3], ["A", "B", "C"], 1);
/* -> [
["A", "B", "C"],
["A", "C", "B"],
["B", "A", "C"],
["B", "C", "A"],
["C", "A", "B"],
["C", "B", "A"]
];
*/
replace(testArray, [1, 2, 3], ["A", "B", "C"], 0);
/* -> [
[ [ 1, 2, 3 ], [ 'A', 'B', 'C' ] ],
[ [ 1, 3, 2 ], [ 'A', 'C', 'B' ] ],
[ [ 2, 1, 3 ], [ 'B', 'A', 'C' ] ],
[ [ 2, 3, 1 ], [ 'B', 'C', 'A' ] ],
[ [ 3, 1, 2 ], [ 'C', 'A', 'B' ] ],
[ [ 3, 2, 1 ], [ 'C', 'B', 'A' ] ]
]
*/
```

## reverseNonMutate()

Creates the same result as JavaScript's built-in `Array.prototype.reverse()`

function, but without mutating the original array it is operating upon.

```
reverseNonMutate([1, 2, 3, 4, 5])
// -> [5, 4, 3, 2, 1]
```

## compareArrays()

Checks if two arrays of arrays are the same.

```
compareArrays([[1, 2, 3, 4], [1, 3, 2, 4], [1, 2, 3, 4], [1, 3, 2, 4]])
// -> true`
```

## cyclicModulo()

A modulo function that wraps minus numbers back into a range between 0 and the modulo

```
cyclicModulo(-2, 5)
// -> 3`
cyclicModulo(7, 5)
// -> 2
```

## factorial()

Calcuates factorials.

```
factorial(4)
// -> 24`
```