# permutation-engine

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

``npm install permutation-engine``

# Permutation Engine

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

## Installation

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

Using npm:

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

## Example problem

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 problem is permutational

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

## The permutation for a number

### The first permutation

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()`:

``````var permutationEngine=require('permutation-engine');
var engine=new permutationEngine(9);
var perm=engine.initialPerm();
console.log('the initial permutation is: '+perm);
``````

Output:

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

The `initialPerm()` function is equivalent to:

``````var perm=engine.index2perm(0);
``````

### The last permutation

The last number 362 879 is mapped to:

``````[ 9 8 7 6 5 4 3 2 1 ]
``````
``````var engine=new permutationEngine(9);
var perm=engine.lastPerm();
console.log('the last permutation is: '+perm);
``````

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:

``````var perm=engine.index2perm(362879);
``````

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

``````var perm=engine.index2perm(engine.indexCount);
``````

### The permutation for any number

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:

``````var engine=new permutationEngine(9);
var perm=engine.index2perm(247);
console.log('index 247 is mapped to: '+perm);
var perm=engine.index2perm(248);
console.log('index 248 is mapped to: '+perm);
``````

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.

## The number for a permutation

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)`:

``````var engine=new permutationEngine(9);
var index=engine.perm2index([ 1,2,8,6,5,4,7,3,9 ]);
console.log('permutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: '+index);
``````

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.

## The next permutation in a row

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:

``````var engine=new permutationEngine(9);
var next=engine.nextPerm([ 1,2,8,6,5,4,7,3,9 ]);
var index=engine.perm2index(next);
console.log('the next permutation for [ 1 2 8 6 5 4 7 3 9 ] is : '+next+' with index: '+index);
``````

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
``````

## Skipping a range of permutations

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

``````var engine=new permutationEngine(9);
var next=engine.skipForward([ 1,2,8,6,5,4,7,3,9 ],3);
var index=engine.perm2index(next);
console.log('the next interesting permutation for [ 1 2 8 6 5 4 7 3 9 ] is :
'+next+' with index: '+index);
``````

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.

## Solution for the example problem

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

``````var solutions=0;
var evaluations=0;
perm=engine.initialPerm();

while(perm!=null)
{
evaluations++;

//check if the first horizontal block is compliant; skip the entire range, if not.
if(sum_horizontal_block(perm,1)!=15) { perm=engine.skipForward(perm,3); continue; }

//check if the second horizontal block is compliant; skip the entire range, if not.
if(sum_horizontal_block(perm,2)!=15) { perm=engine.skipForward(perm,6); continue; }

if(is_solution(perm))
{
solutions++;
console.log('solution:'+solutions);
print_matrix(perm);
}
perm=engine.nextPerm(perm);
}

console.log('permutations:'+engine.indexCount);
console.log('evaluated:'+evaluations);
var evaluated_perc=(evaluations/engine.indexCount*100).toFixed(2);
console.log('evaluated perc:'+evaluated_perc+'%');
``````

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.

## API Summary

 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.