# permutation-engine

Javascript library for mapping permutations onto numbers which allows for looping through a set of permutations and skipping ranges

# Permutation Engine

NodeJS javascript library for mapping permutations onto numbers and looping and skipping through permutations.

Permutation Engine can be installed for Node using `npm`.

Using npm:

``````npm install permutation-engine
``````

Consider the following table:

dia1:15 hor1:6 hor2:15 1 2 3 4 5 6 7 8 9

hor1, hor2, and hor3 are the sums for each row; ver1, ver2, and ver3 are the sums for each column; dia1 and dia2 are the sums along the diagonals. We would like to arrange the numbers in the table in such a way that:

``````hor1 = hor2 = hor3 = ver1 = ver2 = ver3 = dia1 = dia2 = 15
``````

The original arrangement in the numbers is:

``````[ 1 2 3 4 5 6 7 8 9 ]
``````

Here are a few other randomly-picked alternatives:

``````[ 1 2 9 4 3 6 8 7 9 ]
[ 9 2 3 4 6 5 7 8 1 ]
[ 1 2 8 6 5 4 7 3 9 ]
``````

There are 9! i.e. 362 880 different permutations possible. However, only a few of these permutations will satisfy the constraint. In order to find these permutations that satisfy the constraint, we want to:

• be able to enumerate them from 0 to 362 879
• avoid checking all different possibilities

Each number between 0 and 362 879 maps to a different permutation.

The first number 0 is mapped to:

``````[ 1 2 3 4 5 6 7 8 9 ]
``````

We can obtain the first permutation with the function `engine.initialPerm()`:

Output:

``````the initial permutation is: 1,2,3,4,5,6,7,8,9
``````

The `initialPerm()` function is equivalent to:

The last number 362 879 is mapped to:

``````[ 9 8 7 6 5 4 3 2 1 ]
``````

Output:

``````the last permutation is: 9,8,7,6,5,4,3,2,1
``````

Calling the `lastPerm()` function is equivalent to calling the `index2perm()` function with the last number:

Or to calling the `index2perm()` function with `engine.indexCount`:

There is a permutation for any number between the first (zero) and the last number (`n!-1`). A permutation P1 is smaller than P2, if by scanning both permutations from left to right, we run into an element that is smaller in P1 than in P2.

For example:

``````247 [1 2 3 6 4 7 ---5--- 9 8]
248 [1 2 3 6 4 7 ---8--- 5 9]
``````

Since 5 is smaller than 8, the combination with index 247 is smaller than the one with index 248. We can use the `engine.index2perm(index)` function to retrieve the permutation for a number:

Output:

``````index 247 is mapped to: 1,2,3,6,4,7,5,9,8
index 248 is mapped to: 1,2,3,6,4,7,8,5,9
``````

You can find a full explanation for the factorial number system in Wikipedia.

We can also find the number for any particular permutation. For example, if we want the number for the permutation:

``````[ 1 2 8 6 5 4 7 3 9 ]
``````

we can call the javascript function `engine.perm2index(perm)`:

Output:

``````permutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: 4016
``````

We can see that it is mapped to index 4016.

Note: We can find the next permutation by looking up its index with `index=engine.perm2index(perm)` and then increment the index with `index++` and then find the permutation for this next index with `perm=engine.index2perm(index)`.

There is also a direct way through the function `engine.nextPerm(perm)` to find the next permutation for a given permutation:

Output:

``````the next permutation for [ 1 2 8 6 5 4 7 3 9 ] is : 1,2,8,6,5,4,7,9,3 with index: 4017
``````

Imagine we are evaluating the permutation [ 1 2 8 6 5 4 7 3 9 ]. We can see that the sum for [ 1 2 8 ] is not equal to 15. In fact, there is no point in evaluating any permutation that starts with [ 1 2 8 ]. We can use the `next=skipForward([1,2,8,6,5,4,7,3,9],3)` function call to skip the range with prefix [ 1 2 8 ]. The next permutation will start with the successor prefix for [ 1 2 8 ]; in this case [ 1 2 9 ].

Output:

``````the next interesting permutation for [ 1 2 8 6 5 4 7 3 9 ] is : 1,2,9,3,4,5,6,7,8 with index: 4320
``````

Without skipping ranges of permutations, a permutational problem is always NP-complete. The potential total number of evaluations is `n!`. This usually means that the problem cannot be solved for larger dimensions. However, by judiciously skipping entire ranges of permutations, it may be possible to solve a large permutational problem anyway.

The earlier you can detect that a range is invalid, the better. For example, it is better to detect that the following prefix is invalid:

``````[ 1 2 8 ] [ . . . . . . ]  6!=720 possibilities skipped
``````

than only seeing it later:

``````[ 1 2 8 6 5 4 ] [ . . . ]  only 3!=6 possibilities skipped
``````

For example, solving the Travelling salesman problem amounts to discovering a permutation-skipping strategy leaving a number of permutations to evaluate that does not grow factorially with the number of cities.

You can find the complete solution in the file `test/test-3x3.js`.

Output:

``````solution:1
2 7 6
9 5 1
4 3 8
solution:2
2 9 4
7 5 3
6 1 8
...
(There are 8 solutions in total)
...
permutations:362880
evaluated:8376
evaluated perc:2.31%
``````

As you can see, the skipping strategy implemented, brought down the number of permutations to evaluate from 362 880 to 8 376, i.e. to around 2% of the total.

 1. perm = initialPerm() Returns the first permutation. 2. perm = lastPerm() Returns the last permutation. 3. perm = index2perm(index) Returns the permutation for an index. 4. index = perm2index(perm) Returns the index for a permutation. 5. next = nextPerm(perm) Returns the next permutation. 6. next = skipForward(perm, prefixSize) Returns the next permutation by skipping the range prefixed by prefixSize number of elements in the permutation perm supplied.
``````Copyright (c) 2012 Erik Poupaert.