{"_id":"permutation-engine","_rev":"33-e80b8df5c315a4184b0107238e423acb","name":"permutation-engine","description":"Javascript library for mapping permutations onto numbers which allows for looping through a set of permutations and skipping ranges","dist-tags":{"latest":"0.1.5"},"versions":{"0.1.2":{"name":"permutation-engine","version":"0.1.2","description":"Javascript library for mapping permutations onto numbers which allows for looping through a set of permutations and skipping ranges","author":{"name":"Erik Poupaert","email":"erik@sankuru.biz","url":"https://github.com/eriksank/permutation-engine"},"main":"lib/engine.js","scripts":{"test":"test/test-all.js"},"repository":{"type":"git","url":"git://github.com/eriksank/permutation-engine.git"},"keywords":["permutation"],"license":"LGPL","_id":"permutation-engine@0.1.2","dependencies":{},"devDependencies":{},"optionalDependencies":{},"engines":{"node":"*"},"_engineSupported":true,"_npmVersion":"1.1.4","_nodeVersion":"v0.6.12","_defaultsLoaded":true,"_from":"Permutation-engine@0.1.x","_npmUser":{"name":"eriksank","email":"erik@sankuru.biz"},"dist":{"shasum":"c69957975414e34cbd3142b8482e5bd2384272ea","tarball":"https://registry.npmjs.org/permutation-engine/-/permutation-engine-0.1.2.tgz","integrity":"sha512-lsjUt03LmV+zdql+jNrFRjuhsWd9hvDoYOYeXWISwcjhnWQV7XKBV8MDwM4laOSGYzQeMuR7R3TMuV49ioci1Q==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCJ9nYCFOUGxGjKUQNw6HggRexOz8BLX4zq6jhspwQeYQIhAI+ODis9Vmjq9W+ECKhN/slEH+r+X+//fpwuv+iBrdNc"}]},"maintainers":[{"name":"eriksank","email":"erik@sankuru.biz"}],"directories":{}},"0.1.4":{"name":"permutation-engine","version":"0.1.4","description":"Javascript library for mapping permutations onto numbers which allows for looping through a set of permutations and skipping ranges","author":{"name":"Erik Poupaert","email":"erik@sankuru.biz","url":"https://github.com/eriksank/permutation-engine"},"main":"lib/permutation-engine.js","scripts":{"test":"test/test-all.js"},"repository":{"type":"git","url":"git://github.com/eriksank/permutation-engine.git"},"keywords":["permutation"],"license":"LGPL","_id":"permutation-engine@0.1.4","dependencies":{},"devDependencies":{},"optionalDependencies":{},"engines":{"node":"*"},"_engineSupported":true,"_npmVersion":"1.1.4","_nodeVersion":"v0.6.12","_defaultsLoaded":true,"_from":"Permutation-engine@0.1.x","_npmUser":{"name":"eriksank","email":"erik@sankuru.biz"},"dist":{"shasum":"fbb718de29bc9c036dd572093e638efb0874f684","tarball":"https://registry.npmjs.org/permutation-engine/-/permutation-engine-0.1.4.tgz","integrity":"sha512-NdWZMKTCrO4t/PJoQDdTYZzZowZvbVVOP4MSYFZEWoHHr99DcvZzvzslHx4fPceuZIY+deh9anoVHWbjZPqpRQ==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQC5bIqyZKDDYz/3ASOAydLeH50/e7pKmyzdSlApC+/CYAIhAL73xq00XsVJ9SGs3AP+Y2LiZcVTAWxajVRA7X3NvuWo"}]},"maintainers":[{"name":"eriksank","email":"erik@sankuru.biz"}],"directories":{}},"0.1.5":{"name":"permutation-engine","version":"0.1.5","description":"Javascript library for mapping permutations onto numbers which allows for looping through a set of permutations and skipping ranges","author":{"name":"Erik Poupaert","email":"erik@sankuru.biz","url":"https://github.com/eriksank/permutation-engine"},"main":"lib/permutation-engine.js","scripts":{"test":"test/test-all.js"},"repository":{"type":"git","url":"https://github.com/eriksank/permutation-engine.git"},"keywords":["permutation"],"license":"LGPL","_id":"permutation-engine@0.1.5","dependencies":{},"devDependencies":{},"optionalDependencies":{},"engines":{"node":"*"},"_engineSupported":true,"_npmVersion":"1.1.65","_nodeVersion":"v0.6.12","_defaultsLoaded":true,"_from":"Permutation-engine@0.1.x","readme":"Permutation Engine\n==================\n\nNodeJS javascript library for mapping permutations onto numbers and looping and skipping through permutations.\n\nInstallation\n------------\n\nPermutation Engine can be installed for [Node](http://nodejs.org) using [`npm`](http://github.com/isaacs/npm/).\n\nUsing npm:\n\n    npm install permutation-engine\n\n\nExample problem\n---------------\n\nConsider the following table:\n\n<table>\n  <tr>\n    <td></td>\n    <td></td>\n    <td></td>\n    <th>dia1:15</th>\n  </tr>\n  <tr>\n    <td>1</td>\n    <td>2</td>\n    <td>3</td>\n    <th>hor1:6</th>\n  </tr>\n  <tr>\n    <td>4</td>\n    <td>5</td>\n    <td>6</td>\n    <th>hor2:15</th>\n  </tr>\n  <tr>\n    <td>7</td>\n    <td>8</td>\n    <td>9</td>\n    <th>hor3:24</th>\n  </tr>\n  <tr>\n    <th>ver1:12</th>\n    <th>ver2:15</th>\n    <th>ver3:18</th>\n    <th>dia2:15</th>\n  </tr>\n</table>\n\n**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:\n\n\thor1 = hor2 = hor3 = ver1 = ver2 = ver3 = dia1 = dia2 = 15\n\n\nThe problem is permutational\n----------------------------\n\nThe original arrangement in the numbers is: \n\n\t[ 1 2 3 4 5 6 7 8 9 ]\n\nHere are a few other randomly-picked alternatives:\n\n\t[ 1 2 9 4 3 6 8 7 9 ]\n\t[ 9 2 3 4 6 5 7 8 1 ]\n\t[ 1 2 8 6 5 4 7 3 9 ]\n\nThere 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:\n\n- be able to enumerate them from **0** to **362 879**\n- avoid checking all different possibilities\n\n\nThe permutation for a number\n----------------------------\n\n###The first permutation\n\nEach number between **0** and **362 879** maps to a different permutation.\n\nThe first number **0** is mapped to:\n\n\t[ 1 2 3 4 5 6 7 8 9 ]\n\nWe can obtain the first permutation with the function `engine.initialPerm()`:\n\n```javascript\nvar permutationEngine=require('permutation-engine');\nvar engine=new permutationEngine(9); \nvar perm=engine.initialPerm();\nconsole.log('the initial permutation is: '+perm);\n```\nOutput:\n\n\tthe initial permutation is: 1,2,3,4,5,6,7,8,9\n\nThe `initialPerm()` function is equivalent to:\n\n```javascript\nvar perm=engine.index2perm(0);\n```\n\n###The last permutation\n\nThe last number **362 879** is mapped to:\n\n\t[ 9 8 7 6 5 4 3 2 1 ]\n\n```javascript\nvar engine=new permutationEngine(9); \nvar perm=engine.lastPerm();\nconsole.log('the last permutation is: '+perm);\n```\n\nOutput:\n\n\tthe last permutation is: 9,8,7,6,5,4,3,2,1\n\n\nCalling the `lastPerm()` function is equivalent to calling the `index2perm()` function with the last number:\n\n```javascript\nvar perm=engine.index2perm(362879);\n```\n\nOr to calling the `index2perm()` function with `engine.indexCount`:\n\n```javascript\nvar perm=engine.index2perm(engine.indexCount);\n```\n\n###The permutation for any number\n\nThere 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_. \n\nFor example:\n\n\t247 [1 2 3 6 4 7 ---5--- 9 8]\n\t248 [1 2 3 6 4 7 ---8--- 5 9]\n\nSince **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:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar perm=engine.index2perm(247);\nconsole.log('index 247 is mapped to: '+perm);\nvar perm=engine.index2perm(248);\nconsole.log('index 248 is mapped to: '+perm);\n```\n\nOutput:\n\n\tindex 247 is mapped to: 1,2,3,6,4,7,5,9,8\n\tindex 248 is mapped to: 1,2,3,6,4,7,8,5,9\n\n\nYou can find a full explanation for the [factorial number system](http://en.wikipedia.org/wiki/Factoradic) in Wikipedia.\n\n\nThe number for a permutation\n----------------------------\n\nWe can also find the number for any particular permutation. For example, if we want the number for the permutation:\n\n\t[ 1 2 8 6 5 4 7 3 9 ]\n\nwe can call the javascript function `engine.perm2index(perm)`:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar index=engine.perm2index([ 1,2,8,6,5,4,7,3,9 ]);\nconsole.log('permutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: '+index);\n```\n\nOutput:\n\n\tpermutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: 4016\n\nWe can see that it is mapped to index **4016**.\n\n\nThe next permutation in a row\n-----------------------------\n\n_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)`._\n\nThere is also a direct way through the function `engine.nextPerm(perm)` to find the next permutation for a given permutation:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar next=engine.nextPerm([ 1,2,8,6,5,4,7,3,9 ]);\nvar index=engine.perm2index(next);\nconsole.log('the next permutation for [ 1 2 8 6 5 4 7 3 9 ] is : '+next+' with index: '+index);\n```\n\nOutput:\n\n\tthe 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\n\n\nSkipping a range of permutations\n--------------------------------\n\nImagine 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 ]**.\n\n```javascript\nvar engine=new permutationEngine(9); \nvar next=engine.skipForward([ 1,2,8,6,5,4,7,3,9 ],3);\nvar index=engine.perm2index(next);\nconsole.log('the next interesting permutation for [ 1 2 8 6 5 4 7 3 9 ] is : \n\t'+next+' with index: '+index);\n```\n\nOutput:\n\n\tthe 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\n\nWithout skipping ranges of permutations, a permutational problem is always [NP-complete](http://en.wikipedia.org/wiki/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.\n\nThe earlier you can detect that a range is invalid, the better. For example, it is better to detect that the following prefix is invalid:\n\n\t[ 1 2 8 ] [ . . . . . . ]  6!=720 possibilities skipped\n\nthan only seeing it later:\n\n\t[ 1 2 8 6 5 4 ] [ . . . ]  only 3!=6 possibilities skipped \n\n\nFor example, solving the [Travelling salesman problem](http://en.wikipedia.org/wiki/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.\n\n\nSolution for the example problem\n--------------------------------\n\nYou can find the complete solution in the file `test/test-3x3.js`. \n\n```javascript\nvar solutions=0;\nvar evaluations=0;\nperm=engine.initialPerm();\n\nwhile(perm!=null)\n{\n\tevaluations++;\n\n\t//check if the first horizontal block is compliant; skip the entire range, if not.\n\tif(sum_horizontal_block(perm,1)!=15) { perm=engine.skipForward(perm,3); continue; }\n\n\t//check if the second horizontal block is compliant; skip the entire range, if not.\n\tif(sum_horizontal_block(perm,2)!=15) { perm=engine.skipForward(perm,6); continue; }\n\n\tif(is_solution(perm))\n\t{\n\t\tsolutions++;\n\t\tconsole.log('solution:'+solutions);\n\t\tprint_matrix(perm);\n\t}\n\tperm=engine.nextPerm(perm);\n}\n\nconsole.log('permutations:'+engine.indexCount);\nconsole.log('evaluated:'+evaluations);\nvar evaluated_perc=(evaluations/engine.indexCount*100).toFixed(2);\nconsole.log('evaluated perc:'+evaluated_perc+'%');\n\n```\n\nOutput:\n\n\tsolution:1\n\t2 7 6\n\t9 5 1\n\t4 3 8\n\tsolution:2\n\t2 9 4\n\t7 5 3\n\t6 1 8\n\t...\n\t(There are 8 solutions in total)\n\t...\n\tpermutations:362880\n\tevaluated:8376\n\tevaluated perc:2.31%\n\n\nAs 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.\n\n\nAPI Summary\n-----------\n\n<table>\n\n<tr>\n<td>\n1. <i>perm = initialPerm()</i>\n</td>\n<td>\nReturns the first permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n2. <i>perm = lastPerm()</i>\n</td>\n<td>\nReturns the last permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n3. <i>perm = index2perm(index)</i>\n</td>\n<td>\nReturns the permutation for an index.\n</td>\n</tr>\n\n<tr>\n<td>\n4. <i>index = perm2index(perm)</i>\n</td>\n<td>\nReturns the index for a permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n5. <i>next = nextPerm(perm)</i>\n</td>\n<td>\nReturns the next permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n6. <i>next = skipForward(perm, prefixSize)</i>\n</td>\n<td>\nReturns the next permutation by skipping the range prefixed by <i>prefixSize</i> number of elements in the permutation <i>perm</i> supplied.\n</td>\n</tr>\n\n</table>\n\n\nLicense\n-------\n\tCopyright (c) 2012 Erik Poupaert.\n\tLicensed under the Library General Public License (LGPL).\n","readmeFilename":"README.md","dist":{"shasum":"64ee5a1becaf237d80beace0952197ac45e744d3","tarball":"https://registry.npmjs.org/permutation-engine/-/permutation-engine-0.1.5.tgz","integrity":"sha512-cQuY6ZrF08Ee6mBczEhPjlZ5WdP83222IujjsOabWwFM8aCWJziLb29QlyI4QtiM4RHmrRL5PBlDzvV4qPiJdg==","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEUCIQClB1hztMvIsRTh4emr9S557sJuYFDX7WOvl5GM6gl3kgIgVK7AX3JD4kZ4yzVQrgt3YCkz9AHyW0YtRS/Vw/FI4bQ="}]},"_npmUser":{"name":"eriksank","email":"erik@sankuru.biz"},"maintainers":[{"name":"eriksank","email":"erik@sankuru.biz"}]}},"readme":"Permutation Engine\n==================\n\nNodeJS javascript library for mapping permutations onto numbers and looping and skipping through permutations.\n\nInstallation\n------------\n\nPermutation Engine can be installed for [Node](http://nodejs.org) using [`npm`](http://github.com/isaacs/npm/).\n\nUsing npm:\n\n    npm install permutation-engine\n\n\nExample problem\n---------------\n\nConsider the following table:\n\n<table>\n  <tr>\n    <td></td>\n    <td></td>\n    <td></td>\n    <th>dia1:15</th>\n  </tr>\n  <tr>\n    <td>1</td>\n    <td>2</td>\n    <td>3</td>\n    <th>hor1:6</th>\n  </tr>\n  <tr>\n    <td>4</td>\n    <td>5</td>\n    <td>6</td>\n    <th>hor2:15</th>\n  </tr>\n  <tr>\n    <td>7</td>\n    <td>8</td>\n    <td>9</td>\n    <th>hor3:24</th>\n  </tr>\n  <tr>\n    <th>ver1:12</th>\n    <th>ver2:15</th>\n    <th>ver3:18</th>\n    <th>dia2:15</th>\n  </tr>\n</table>\n\n**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:\n\n\thor1 = hor2 = hor3 = ver1 = ver2 = ver3 = dia1 = dia2 = 15\n\n\nThe problem is permutational\n----------------------------\n\nThe original arrangement in the numbers is: \n\n\t[ 1 2 3 4 5 6 7 8 9 ]\n\nHere are a few other randomly-picked alternatives:\n\n\t[ 1 2 9 4 3 6 8 7 9 ]\n\t[ 9 2 3 4 6 5 7 8 1 ]\n\t[ 1 2 8 6 5 4 7 3 9 ]\n\nThere 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:\n\n- be able to enumerate them from **0** to **362 879**\n- avoid checking all different possibilities\n\n\nThe permutation for a number\n----------------------------\n\n###The first permutation\n\nEach number between **0** and **362 879** maps to a different permutation.\n\nThe first number **0** is mapped to:\n\n\t[ 1 2 3 4 5 6 7 8 9 ]\n\nWe can obtain the first permutation with the function `engine.initialPerm()`:\n\n```javascript\nvar permutationEngine=require('engine.js');\nvar engine=new permutationEngine(9); \nvar perm=engine.initialPerm();\nconsole.log('the initial permutation is: '+perm);\n```\nOutput:\n\n\tthe initial permutation is: 1,2,3,4,5,6,7,8,9\n\nThe `initialPerm()` function is equivalent to:\n\n```javascript\nvar perm=engine.index2perm(0);\n```\n\n###The last permutation\n\nThe last number **362 879** is mapped to:\n\n\t[ 9 8 7 6 5 4 3 2 1 ]\n\n```javascript\nvar engine=new permutationEngine(9); \nvar perm=engine.lastPerm();\nconsole.log('the last permutation is: '+perm);\n```\n\nOutput:\n\n\tthe last permutation is: 9,8,7,6,5,4,3,2,1\n\n\nCalling the `lastPerm()` function is equivalent to calling the `index2perm()` function with the last number:\n\n```javascript\nvar perm=engine.index2perm(362879);\n```\n\nOr to calling the `index2perm()` function with `engine.indexCount`:\n\n```javascript\nvar perm=engine.index2perm(engine.indexCount);\n```\n\n###The permutation for any number\n\nThere 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_. \n\nFor example:\n\n\t247 [1 2 3 6 4 7 ---5--- 9 8]\n\t248 [1 2 3 6 4 7 ---8--- 5 9]\n\nSince **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:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar perm=engine.index2perm(247);\nconsole.log('index 247 is mapped to: '+perm);\nvar perm=engine.index2perm(248);\nconsole.log('index 248 is mapped to: '+perm);\n```\n\nOutput:\n\n\tindex 247 is mapped to: 1,2,3,6,4,7,5,9,8\n\tindex 248 is mapped to: 1,2,3,6,4,7,8,5,9\n\n\nYou can find a full explanation for the [factorial number system](http://en.wikipedia.org/wiki/Factoradic) in Wikipedia.\n\n\nThe number for a permutation\n----------------------------\n\nWe can also find the number for any particular permutation. For example, if we want the number for the permutation:\n\n\t[ 1 2 8 6 5 4 7 3 9 ]\n\nwe can call the javascript function `engine.perm2index(perm)`:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar index=engine.perm2index([ 1,2,8,6,5,4,7,3,9 ]);\nconsole.log('permutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: '+index);\n```\n\nOutput:\n\n\tpermutation [ 1 2 8 6 5 4 7 3 9 ] is mapped to: 4016\n\nWe can see that it is mapped to index **4016**.\n\n\nThe next permutation in a row\n-----------------------------\n\n_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)`._\n\nThere is also a direct way through the function `engine.nextPerm(perm)` to find the next permutation for a given permutation:\n\n```javascript\nvar engine=new permutationEngine(9); \nvar next=engine.nextPerm([ 1,2,8,6,5,4,7,3,9 ]);\nvar index=engine.perm2index(next);\nconsole.log('the next permutation for [ 1 2 8 6 5 4 7 3 9 ] is : '+next+' with index: '+index);\n```\n\nOutput:\n\n\tthe 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\n\n\nSkipping a range of permutations\n--------------------------------\n\nImagine 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 ]**.\n\n```javascript\nvar engine=new permutationEngine(9); \nvar next=engine.skipForward([ 1,2,8,6,5,4,7,3,9 ],3);\nvar index=engine.perm2index(next);\nconsole.log('the next interesting permutation for [ 1 2 8 6 5 4 7 3 9 ] is : \n\t'+next+' with index: '+index);\n```\n\nOutput:\n\n\tthe 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\n\nWithout skipping ranges of permutations, a permutational problem is always [NP-complete](http://en.wikipedia.org/wiki/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.\n\nThe earlier you can detect that a range is invalid, the better. For example, it is better to detect that the following prefix is invalid:\n\n\t[ 1 2 8 ] [ . . . . . . ]  6!=720 possibilities skipped\n\nthan only seeing it later:\n\n\t[ 1 2 8 6 5 4 ] [ . . . ]  only 3!=6 possibilities skipped \n\n\nFor example, solving the [Travelling salesman problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem) amounts to discovering a permutation-skipping strategy leaving the number of permutations to evaluate that does not grow factorially with the number of cities.\n\n\nSolution for the example problem\n--------------------------------\n\nYou can find the complete solution in the file `test/test-3x3.js`. \n\n```javascript\nvar solutions=0;\nvar evaluations=0;\nperm=engine.initialPerm();\n\nwhile(perm!=null)\n{\n\tevaluations++;\n\n\t//check if the first horizontal block is compliant; skip the entire range, if not.\n\tif(sum_horizontal_block(perm,1)!=15) { perm=engine.skipForward(perm,3); continue; }\n\n\t//check if the second horizontal block is compliant; skip the entire range, if not.\n\tif(sum_horizontal_block(perm,2)!=15) { perm=engine.skipForward(perm,6); continue; }\n\n\tif(is_solution(perm))\n\t{\n\t\tsolutions++;\n\t\tconsole.log('solution:'+solutions);\n\t\tprint_matrix(perm);\n\t}\n\tperm=engine.nextPerm(perm);\n}\n\nconsole.log('permutations:'+engine.indexCount);\nconsole.log('evaluated:'+evaluations);\nvar evaluated_perc=(evaluations/engine.indexCount*100).toFixed(2);\nconsole.log('evaluated perc:'+evaluated_perc+'%');\n\n```\n\nOutput:\n\n\tsolution:1\n\t2 7 6\n\t9 5 1\n\t4 3 8\n\tsolution:2\n\t2 9 4\n\t7 5 3\n\t6 1 8\n\t...\n\t(There are 8 solutions in total)\n\t...\n\tpermutations:362880\n\tevaluated:8376\n\tevaluated perc:2.31%\n\n\nAs 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.\n\n\nAPI Summary\n-----------\n\n<table>\n\n<tr>\n<td>\n1. <i>perm = initialPerm()</i>\n</td>\n<td>\nReturns the first permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n2. <i>perm = lastPerm()</i>\n</td>\n<td>\nReturns the last permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n3. <i>perm = index2perm(index)</i>\n</td>\n<td>\nReturns the permutation for an index.\n</td>\n</tr>\n\n<tr>\n<td>\n4. <i>index = perm2index(perm)</i>\n</td>\n<td>\nReturns the index for a permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n5. <i>next = nextPerm(perm)</i>\n</td>\n<td>\nReturns the next permutation.\n</td>\n</tr>\n\n<tr>\n<td>\n6. <i>next = skipForward(perm, prefixSize)</i>\n</td>\n<td>\nReturns the next permutation by skipping the range prefixed by <i>prefixSize</i> number of elements in the permutation <i>perm</i> supplied.\n</td>\n</tr>\n\n</table>\n\n\nLicense\n-------\n\tCopyright (c) 2012 Erik Poupaert.\n\tLicensed under the Library General Public License (LGPL).\n","maintainers":[{"name":"eriksank","email":"erik@sankuru.biz"}],"time":{"modified":"2022-06-23T18:44:18.013Z","created":"2012-11-13T11:11:32.658Z","0.1.2":"2012-11-13T11:11:37.519Z","0.1.4":"2012-11-14T23:39:16.833Z","0.1.5":"2012-11-25T21:28:10.340Z"},"author":{"name":"Erik Poupaert","email":"erik@sankuru.biz","url":"https://github.com/eriksank/permutation-engine"},"repository":{"type":"git","url":"https://github.com/eriksank/permutation-engine.git"}}