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")
• 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.

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[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.

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

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 A so as to reduce this formulation to the general one stated above.

One way of constructing a set A is to build it up element by element. Suppose that a1, ... ,ak-1 have been chosen. The given restrictions will then require that ak; belong to some subset Sk of U. If Sk is not empty an ak, can be chosen and the building-up process continued; if Sk, is empty one must back-track and change one of the previous a’s. To do this systematically we shall assume that the elements of U have been linearly ordered, and shall always choose ak to be the least element of Sk. If Sk is empty we return to Sk-1 and change ak-1 to the next larger element of Sk-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 Step s + 1 will follow Step s unless otherwise specified.

General program.

1. Set k = 1.
2. Set Sk = S1.
3. If Sk is empty jump to 9.
4. Set ak equal to the smallest element of Sk.
5. If k = n jump to 14.
6. Replace k by k + 1.
7. Compute Sk.
8. Jump to 3.
9. If k = 1, stop.
10. Replace k by k — 1.
11. Compute Sk.
12. Replace Sk by Sk ∩ {a| a > ak}.
13. Jump to 3.
14. Record A = {a1, ... , an}.
15. 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 set A is 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 < n but 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 general n, 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 a1, a2, ..., an

of the numbers 0(1)n — 1 we strike out a; and reduce by unity all the marks which exceed a1, we get a new permutation

α1, α2, ..., αn-1

of the numbers 0(1)n — 2, which we may denote by

M (a1, a2, ..., an).

If we now define a rank function > R (a1, a2, ..., an) recursively by

R(0) = 0,

R(> M (a1, a2, ..., an).) = a1(n — 1)! + R(M (a1, a2, ..., an))

it is seen that R is nothing but the rank or serial number of the permutation (a1, a3, ..., an) 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 by a1(n — 1)! permutations whose first mark is less than a1. Among those permutations which begin with a1, ours has rank R(M (a1, a2, ..., an)). 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

Sn—1, Sn-2, ..., S2, S1

we may reconstruct the permutation having this rank. Beginning with 0 we affix S1 and in case S1 is 0, we increase the original 0 to 1. Thus we get

O 1 if S1 = 0,

1 0 if S1 = 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 mark k > 0, ask how many of the k marks less than k actually follow k. Denoting this number by Sx we see at once that

Sn-1, Sn-2, ... S2, S1

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.

| S6 | S5 | S4 | S3 | S2 | S1 | | | | | | | | | | --------------- | --------------- | --------------- | --------------- | --------------- | --------------- | --- | --- | --- | --- | --- | --- | --- | --- | | 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.

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:

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

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

Usage

peckSchrack(4) will generate all possible permutations of the array [1, 2, 3, 4].

Howell (1962) [ACM87: PERMUTATION]

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:

where reverse() "inverts the order of the elements in P[1],....,P[i]:

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

Usage

schrackShimrat(4);

Use arrays containing: only numbers

Eaves (1962) [ACM130: Permute]

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:

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:

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

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:

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, if n = 4, our initial data are as follows:

< < < <
1 2 3 4

An integer k is mobile if there exists an integer smaller than k adjacent to k on the side where the direction of k points 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 m switch 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:

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:

Usage

langdon(4);

Boothroyd (1967) [BCJ30]

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

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:

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 are n, n − 1 , ... , 2. The second indices are remainders when i is successively divided by n, n− 1 , ... , 2, plus one. For example, here are the calculations for i = 92 and n = 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 i into the object of rank i. In remainder order, the unranking and ranking algorithms use O(n) arithmetic operations on values that can be as large as n! ."

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`