# historical-permutations ## A JavaScript library of historical permutation algorithms from 1956 to the present day. [![Build Status](https://travis-ci.com/dpocknee/historical-permutations.svg?branch=master)](https://travis-ci.com/dpocknee/historical-permutations) [![Maintenance](https://img.shields.io/badge/Maintained%3F-yes-green.svg)](https://github.com/dpocknee/historical-permutations/graphs/commit-activity) [![Generic badge](https://img.shields.io/badge/Contributions-Welcome-green.svg)](https://shields.io/) 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): ```JavaScript 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: ```JavaScript 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: ```JavaScript 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](https://www.npmjs.com/package/historical-permutations) - github: [https://github.com/dpocknee/historical-permutations](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](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 ```javaScript 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 ```javaScript 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 ```javaScript 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 _a_1, ... ,_a_k-1 have been chosen. The given restrictions will > then require that _a_k; belong to some subset _S_k of _U_. If _S_k is not empty an _a_k, can be chosen and the building-up process continued; if _S_k, 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 _a_k to be the least element of _S_k. If _S_k is empty we return to _S_k-1 and change _a_k-1 to the next larger element of _S_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 Step _s_ + 1 will follow Step _s_ unless otherwise specified. > > General program. > > 1. Set _k_ = 1. > 2. Set _S_k = _S_1. > 3. If _S_k is empty jump to 9. > 4. Set _a_k equal to the smallest element of _S_k. > 5. If _k_ = _n_ jump to 14. > 6. Replace _k_ by _k_ + 1. > 7. Compute _S_k. > 8. Jump to 3. > 9. If _k_ = 1, stop. > 10. Replace _k_ by _k_ — 1. > 11. Compute _S_k. > 12. Replace _S_k by _S_k ∩ {a| _a_ > _a_k}. > 13. Jump to 3. > 14. Record _A_ = {_a_1, ... , _a_n}. > 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 > _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 exceed _a_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 _R_ is 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 by _a_1(_n_ — 1)! permutations whose first mark is less than _a_1. Among those permutations which begin with _a_1, ours has rank _R_(_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, 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 > > _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 ```javaScript 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 ```javaScript 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: 

procedure PERM (x, n); value n;
integer n; array x;
comment This algorithm was inspired by the procedure 
PERMUTE of Peck and Schrack (Algorithm 86, Comm. ACM
Apr. 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 made
true.

The excuse for adding PERM to the growing pile of permuta-
tion generators is that, at the expense of some extra own storage,
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 array p, d[2:n]; integer k,q; real t;
  if first then initialize:
  begin for k := 2 step 1 until n do 
    begin p[k] := 0; d[k] := 1 end;
    first := false
  end initialize;
  k := 0;
  INDEX: p[n] := q := p[n] + d[n];
    if q = n then
    begin d[n] := —1; go to LOOP end;
    if q ≠ O then go to TRANSPOSE;
    d[n] := 1; k := k + 1;
    LOOP: if n > 2 then begin
      comment Note that n was called by value;
      n := n— 1; go to INDEX end LOOP;
  Final exit: q := 1; first := true;
  TRANSPOSE: q := q + k; t := x[q];
    x[q] := x[q + 1]; := t
end PERM;

Trotter, H. F. "Algorithm 115: Perm". In:
Communications of the ACM 5.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, 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: ```JavaScript 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] 

procedure perm (x, n); value n; integer n; array x;
begin own integer array q[3:10]; integer k, m;
    real t; own boolean odd;
    if first then begin odd := true;
          if n> 2 then begin first := false;
          for m := 3 step 1 until 2 do
          q[m] := 1   end
        end
    if odd then begin odd := false;
          t := x[1]; x[1] := x[2]; x[2] := t;
          goto finish
        end;
    odd := true; k := 3;
oop:   m := q[k]; if m = k then
    begin if k < n then begin q[k] := 1;
              k := k + 1;
              goto loop
            end
        else begin first := true; goto trinit end
    end;
  q[k] := m + 1;
  trinit: m := 1;
  transpose: t = x[m]; x[m] := x[k]; x[k] := t;
      m := m + 1; k := k — 1;
      if m < k then goto transpose;
finish:  end of procedure perm;

R. J. Ord-Smith "Generation of permutation sequences: Part 1", 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 ```javaScript 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 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](http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html) 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](http://www.gregegan.net/SCIENCE/Superpermutations/Superpermutations.html) ### Usage ```JavaScript 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: ```JavaScript 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. ```JavaScript 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. ```JavaScript 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. ```JavaScript 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. ```JavaScript 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. ```JavaScript 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. ```Javascript 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. ```JavaScript reverseNonMutate([1, 2, 3, 4, 5]) // -> [5, 4, 3, 2, 1] ``` ## compareArrays() Checks if two arrays of arrays are the same. ```javaScript 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 ```javaScript cyclicModulo(-2, 5) // -> 3` cyclicModulo(7, 5) // -> 2 ``` ## factorial() Calcuates factorials. ```javaScript factorial(4) // -> 24` ```