[javascript] Permutations in JavaScript?

I'm trying to write a function that does the following:

• takes an array of integers as an argument (e.g. [1,2,3,4])
• creates an array of all the possible permutations of [1,2,3,4], with each permutation having a length of 4

the function below (I found it online) does this by taking a string as an argument, and returning all the permutations of that string

I could not figure out how to modify it to make it work with an array of integers, (I think this has something to do with how some of the methods work differently on strings than they do on integers, but I'm not sure...)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < chars.length; i++) {
    ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length == 0)
      permArr[permArr.length] = usedChars.join("");
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

Note: I'm looking to make the function return arrays of integers, not an array of strings.

I really need the solution to be in JavaScript. I've already figured out how to do this in python

  let permutations = []

  permutate([], {
    color: ['red', 'green'],
    size: ['big', 'small', 'medium'],
    type: ['saison', 'oldtimer']
  })

  function permutate (currentVals, remainingAttrs) {
    remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => {
      let currentValsNew = currentVals.slice(0)
      currentValsNew.push(attrVal)

      if (Object.keys(remainingAttrs).length > 1) {
        let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs))
        delete remainingAttrsNew[Object.keys(remainingAttrs)[0]]

        permutate(currentValsNew, remainingAttrsNew)
      } else {
        permutations.push(currentValsNew)
      }
    })
  }

Result:

[ 
  [ 'red', 'big', 'saison' ],
  [ 'red', 'big', 'oldtimer' ],
  [ 'red', 'small', 'saison' ],
  [ 'red', 'small', 'oldtimer' ],
  [ 'red', 'medium', 'saison' ],
  [ 'red', 'medium', 'oldtimer' ],
  [ 'green', 'big', 'saison' ],
  [ 'green', 'big', 'oldtimer' ],
  [ 'green', 'small', 'saison' ],
  [ 'green', 'small', 'oldtimer' ],
  [ 'green', 'medium', 'saison' ],
  [ 'green', 'medium', 'oldtimer' ] 
]

Similar in spirit to the Haskell-style solution by @crl, but working with reduce:

function permutations( base ) {
  if (base.length == 0) return [[]]
  return permutations( base.slice(1) ).reduce( function(acc,perm) {
    return acc.concat( base.map( function(e,pos) {
      var new_perm = perm.slice()
      new_perm.splice(pos,0,base[0])
      return new_perm
    }))
  },[])    
}

Here is another "more recursive" solution.

function perms(input) {
  var data = input.slice();
  var permutations = [];
  var n = data.length;

  if (n === 0) {
    return [
      []
    ];
  } else {
    var first = data.shift();
    var words = perms(data);
    words.forEach(function(word) {
      for (var i = 0; i < n; ++i) {
        var tmp = word.slice();
        tmp.splice(i, 0, first)
        permutations.push(tmp);
      }
    });
  }

  return permutations;
}

var str = 'ABC';
var chars = str.split('');
var result = perms(chars).map(function(p) {
  return p.join('');
});

console.log(result);

var output = window.document.getElementById('output');
output.innerHTML = result;

<div id="output"></div>

Output:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]

This is an interesting task and and here is my contribution. It's very simple and fast. If interested please bear with me and read on.

If you would like to this job fast, you definitely have to get yourself into dynamical programming. Which means you should forget about recursive approaches. That's for sure...

OK le_m's code which uses the Heap's method seems to be the fastest so far. Well i haven't got a name for my algorithm, i don't know if it's already been implemented or not but it's very simple and fast. As with all dynamical programming approaches we will start with the simplest problem and go for the final result.

Assuming that we have an array of a = [1,2,3] we will start with

r = [[1]]; // result
t = [];    // interim result

Then follow these three steps;

1. For each item of our r (result) array we will add the next item of the input array.
2. We will rotate each item it's length many times and will store each instance at the interim result array t. (well except for the first one not to waste time with 0 rotation)
3. Once we finish with all items of r the interim array t should hold the next level of results so we make r = t; t = []; and carry on up until the length of the input array a.

So the following are our steps;

r array   | push next item to |  get length many rotations
          |  each sub array   |       of each subarray
-----------------------------------------------------------
[[1]]     |     [[1,2]]       |     [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2],   |     [[1,2,3],     |     [[1,2,3],[2,3,1],[3,1,2],
 [2,1]]   |      [2,1,3]]     |      [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t|                   |
-----------------------------------------------------------

So here is the code

function perm(a){_x000D_
  var r = [[a[0]]],_x000D_
      t = [],_x000D_
      s = [];_x000D_
  if (a.length <= 1) return a;_x000D_
  for (var i = 1, la = a.length; i < la; i++){_x000D_
    for (var j = 0, lr = r.length; j < lr; j++){_x000D_
      r[j].push(a[i]);_x000D_
      t.push(r[j]);_x000D_
      for(var k = 1, lrj = r[j].length; k < lrj; k++){_x000D_
        for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];_x000D_
        t[t.length] = s;_x000D_
        s = [];_x000D_
      }_x000D_
    }_x000D_
    r = t;_x000D_
    t = [];_x000D_
  }_x000D_
  return r;_x000D_
}_x000D_
_x000D_
var arr = [0,1,2,4,5];_x000D_
console.log("The length of the permutation is:",perm(arr).length);_x000D_
console.time("Permutation test");_x000D_
for (var z = 0; z < 2000; z++) perm(arr);_x000D_
console.timeEnd("Permutation test");

In multiple test i have seen it resolving the 120 permutations of [0,1,2,3,4] for 2000 times in 25~35ms.

Answer without the need for a exterior array or additional function

function permutator (arr) {
  var permutations = [];
  if (arr.length === 1) {
    return [ arr ];
  }

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
    for (var j = 0; j < subPerms.length; j++) {
      subPerms[j].unshift(arr[i]);
      permutations.push(subPerms[j]);
    }
  }
  return permutations;
}

Functional answer using flatMap:

const getPermutationsFor = (arr, permutation = []) =>
  arr.length === 0
    ? [permutation]
    : arr.flatMap((item, i, arr) =>
        getPermutationsFor(
          arr.filter((_,j) => j !== i),
          [...permutation, item]
        )
      );

I have improved SiGanteng's answer.

Now it is possible to call permute more than once, because permArr and usedChars are cleared each time.

function permute(input) {
    var permArr = [],
        usedChars = [];
    return (function main() {
        for (var i = 0; i < input.length; i++) {
            var ch = input.splice(i, 1)[0];
            usedChars.push(ch);
            if (input.length == 0) {
                permArr.push(usedChars.slice());
            }
            main();
            input.splice(i, 0, ch);
            usedChars.pop();
        }
        return permArr;
    })();
}

function permute(input) {_x000D_
  var permArr = [],_x000D_
      usedChars = [];_x000D_
  return (function main() {_x000D_
    for (var i = 0; i < input.length; i++) {_x000D_
      var ch = input.splice(i, 1)[0];_x000D_
      usedChars.push(ch);_x000D_
      if (input.length == 0) {_x000D_
        permArr.push(usedChars.slice());_x000D_
      }_x000D_
      main();_x000D_
      input.splice(i, 0, ch);_x000D_
      usedChars.pop();_x000D_
    }_x000D_
    return permArr;_x000D_
  })();_x000D_
}_x000D_
document.write(JSON.stringify(permute([5, 3, 7, 1])));

Some version inspired from Haskell:

perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]

function perms(xs) {
  if (!xs.length) return [[]];
  return xs.flatMap(x => {
    // get permutations of xs without x, then prepend x to each
    return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
  });
  // or this duplicate-safe way, suggested by @M.Charbonnier in the comments
  // return xs.flatMap((x, i) => {
  //   return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]);
  // });
}
document.write(JSON.stringify(perms([1,2,3])));

Quite late. Still just in case if this helps anyone.

function permute(arr) {_x000D_
  if (arr.length == 1) return arr_x000D_
_x000D_
  let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])_x000D_
                              .map(v => [d,v].join(''))).flat()_x000D_
_x000D_
  return res_x000D_
}_x000D_
_x000D_
console.log(permute([1,2,3,4]))

perm = x => x[0] ?  x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]

#!/usr/bin/env node
"use strict";

function perm(arr) {
    if(arr.length<2) return [arr];
    var res = [];
    arr.forEach(function(x, i) {
        perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) {
            res.push([x].concat(a));
        });
    });
    return res;
}

console.log(perm([1,2,3,4]));

This is an implementation of Heap's algorithm (similar to @le_m's), except it's recursive.

function permute_kingzee(arr,n=arr.length,out=[]) {
    if(n == 1) {
        return out.push(arr.slice());
    } else {
        for(let i=0; i<n; i++) {
            permute_kingzee(arr,n-1, out);
            let j = ( n % 2 == 0 ) ? i : 0;
            let t = arr[n-1];
            arr[n-1] = arr[j];
            arr[j] = t;
        }
        return out;
    }
}

It looks like it's quite faster too : https://jsfiddle.net/3brqzaLe/

"use strict";_x000D_
function getPermutations(arrP) {_x000D_
    var results = [];_x000D_
    var arr = arrP;_x000D_
    arr.unshift(null);_x000D_
    var length = arr.length;_x000D_
_x000D_
    while (arr[0] === null) {_x000D_
_x000D_
        results.push(arr.slice(1).join(''));_x000D_
_x000D_
        let less = null;_x000D_
        let lessIndex = null;_x000D_
_x000D_
        for (let i = length - 1; i > 0; i--) {_x000D_
            if(arr[i - 1] < arr[i]){_x000D_
                less = arr[i - 1];_x000D_
                lessIndex = i - 1;_x000D_
                break;_x000D_
            }_x000D_
        }_x000D_
_x000D_
        for (let i = length - 1; i > lessIndex; i--) {_x000D_
            if(arr[i] > less){_x000D_
                arr[lessIndex] = arr[i];_x000D_
                arr[i] = less;_x000D_
                break;_x000D_
            }_x000D_
        }_x000D_
_x000D_
        for(let i = lessIndex + 1; i<length; i++){_x000D_
           for(let j = i + 1; j < length; j++){_x000D_
               if(arr[i] > arr[j] ){_x000D_
                   arr[i] = arr[i] + arr[j];_x000D_
                   arr[j] = arr[i] - arr[j];_x000D_
                   arr[i] = arr[i] - arr[j];_x000D_
               }_x000D_
           }_x000D_
        }_x000D_
    }_x000D_
_x000D_
    return results;_x000D_
}_x000D_
_x000D_
var res = getPermutations([1,2,3,4,5]);_x000D_
var out = document.getElementById('myTxtArr');_x000D_
res.forEach(function(i){ out.value+=i+', '});

textarea{_x000D_
   height:500px;_x000D_
  width:500px;_x000D_
}

<textarea id='myTxtArr'></textarea>

Outputs lexicographically ordered permutations. Works only with numbers. In other case, you have to change the swap method on line 34.

Here's a very short solution, that only works for 1 or 2 long strings. It's a oneliner, and it's blazing fast, using ES6 and not depending on jQuery. Enjoy:

var p = l => l.length<2 ? [l] : l.length==2 ? [l[0]+l[1],l[1]+l[0]] : Function('throw Error("unimplemented")')();

The following very efficient algorithm uses Heap's method to generate all permutations of N elements with runtime complexity in O(N!):

function permute(permutation) {_x000D_
  var length = permutation.length,_x000D_
      result = [permutation.slice()],_x000D_
      c = new Array(length).fill(0),_x000D_
      i = 1, k, p;_x000D_
_x000D_
  while (i < length) {_x000D_
    if (c[i] < i) {_x000D_
      k = i % 2 && c[i];_x000D_
      p = permutation[i];_x000D_
      permutation[i] = permutation[k];_x000D_
      permutation[k] = p;_x000D_
      ++c[i];_x000D_
      i = 1;_x000D_
      result.push(permutation.slice());_x000D_
    } else {_x000D_
      c[i] = 0;_x000D_
      ++i;_x000D_
    }_x000D_
  }_x000D_
  return result;_x000D_
}_x000D_
_x000D_
console.log(permute([1, 2, 3]));

The same algorithm implemented as a generator with space complexity in O(N):

function* permute(permutation) {_x000D_
  var length = permutation.length,_x000D_
      c = Array(length).fill(0),_x000D_
      i = 1, k, p;_x000D_
_x000D_
  yield permutation.slice();_x000D_
  while (i < length) {_x000D_
    if (c[i] < i) {_x000D_
      k = i % 2 && c[i];_x000D_
      p = permutation[i];_x000D_
      permutation[i] = permutation[k];_x000D_
      permutation[k] = p;_x000D_
      ++c[i];_x000D_
      i = 1;_x000D_
      yield permutation.slice();_x000D_
    } else {_x000D_
      c[i] = 0;_x000D_
      ++i;_x000D_
    }_x000D_
  }_x000D_
}_x000D_
_x000D_
// Memory efficient iteration through permutations:_x000D_
for (var permutation of permute([1, 2, 3])) console.log(permutation);_x000D_
_x000D_
// Simple array conversion:_x000D_
var permutations = [...permute([1, 2, 3])];

Performance comparison

Feel free to add your implementation to the following benchmark.js test suite:

function permute_SiGanteng(input) {_x000D_
  var permArr = [],_x000D_
    usedChars = [];_x000D_
_x000D_
  function permute(input) {_x000D_
    var i, ch;_x000D_
    for (i = 0; i < input.length; i++) {_x000D_
      ch = input.splice(i, 1)[0];_x000D_
      usedChars.push(ch);_x000D_
      if (input.length == 0) {_x000D_
        permArr.push(usedChars.slice());_x000D_
      }_x000D_
      permute(input);_x000D_
      input.splice(i, 0, ch);_x000D_
      usedChars.pop();_x000D_
    }_x000D_
    return permArr_x000D_
  }_x000D_
  return permute(input);_x000D_
}_x000D_
_x000D_
function permute_delimited(inputArr) {_x000D_
  var results = [];_x000D_
_x000D_
  function permute(arr, memo) {_x000D_
    var cur, memo = memo || [];_x000D_
    for (var i = 0; i < arr.length; i++) {_x000D_
      cur = arr.splice(i, 1);_x000D_
      if (arr.length === 0) {_x000D_
        results.push(memo.concat(cur));_x000D_
      }_x000D_
      permute(arr.slice(), memo.concat(cur));_x000D_
      arr.splice(i, 0, cur[0]);_x000D_
    }_x000D_
    return results;_x000D_
  }_x000D_
  return permute(inputArr);_x000D_
}_x000D_
_x000D_
function permute_monkey(inputArray) {_x000D_
  return inputArray.reduce(function permute(res, item, key, arr) {_x000D_
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) {_x000D_
      return [item].concat(perm);_x000D_
    }) || item);_x000D_
  }, []);_x000D_
}_x000D_
_x000D_
function permute_Oriol(input) {_x000D_
  var permArr = [],_x000D_
    usedChars = [];_x000D_
  return (function main() {_x000D_
    for (var i = 0; i < input.length; i++) {_x000D_
      var ch = input.splice(i, 1)[0];_x000D_
      usedChars.push(ch);_x000D_
      if (input.length == 0) {_x000D_
        permArr.push(usedChars.slice());_x000D_
      }_x000D_
      main();_x000D_
      input.splice(i, 0, ch);_x000D_
      usedChars.pop();_x000D_
    }_x000D_
    return permArr;_x000D_
  })();_x000D_
}_x000D_
_x000D_
function permute_MarkusT(input) {_x000D_
  function permutate(array, callback) {_x000D_
      function p(array, index, callback) {_x000D_
          function swap(a, i1, i2) {_x000D_
              var t = a[i1];_x000D_
              a[i1] = a[i2];_x000D_
              a[i2] = t;_x000D_
          }_x000D_
          if (index == array.length - 1) {_x000D_
              callback(array);_x000D_
              return 1;_x000D_
          } else {_x000D_
              var count = p(array, index + 1, callback);_x000D_
              for (var i = index + 1; i < array.length; i++) {_x000D_
                  swap(array, i, index);_x000D_
                  count += p(array, index + 1, callback);_x000D_
                  swap(array, i, index);_x000D_
              }_x000D_
              return count;_x000D_
          }_x000D_
      }_x000D_
      if (!array || array.length == 0) {_x000D_
          return 0;_x000D_
      }_x000D_
      return p(array, 0, callback);_x000D_
  }_x000D_
  var result = [];_x000D_
  permutate(input, function(a) {_x000D_
      result.push(a.slice(0));_x000D_
  });_x000D_
  return result;_x000D_
}_x000D_
_x000D_
function permute_le_m(permutation) {_x000D_
  var length = permutation.length,_x000D_
    result = [permutation.slice()],_x000D_
      c = new Array(length).fill(0),_x000D_
      i = 1, k, p;_x000D_
  _x000D_
  while (i < length) {_x000D_
    if (c[i] < i) {_x000D_
      k = i % 2 && c[i],_x000D_
      p = permutation[i];_x000D_
      permutation[i] = permutation[k];_x000D_
      permutation[k] = p;_x000D_
      ++c[i];_x000D_
      i = 1;_x000D_
      result.push(permutation.slice());_x000D_
    } else {_x000D_
      c[i] = 0;_x000D_
      ++i;_x000D_
    }_x000D_
  }_x000D_
  return result;_x000D_
}_x000D_
_x000D_
function permute_Urielzen(arr) {_x000D_
    var finalArr = [];_x000D_
    var iterator = function (arrayTaken, tree) {_x000D_
        for (var i = 0; i < tree; i++) {_x000D_
            var temp = arrayTaken.slice();_x000D_
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);_x000D_
            if (tree >= arr.length) {_x000D_
                finalArr.push(temp);_x000D_
            } else { iterator(temp, tree + 1); }_x000D_
        }_x000D_
    }_x000D_
    iterator(arr, 1); return finalArr;_x000D_
}_x000D_
_x000D_
function permute_Taylor_Hakes(arr) {_x000D_
  var permutations = [];_x000D_
  if (arr.length === 1) {_x000D_
    return [ arr ];_x000D_
  }_x000D_
_x000D_
  for (var i = 0; i <  arr.length; i++) { _x000D_
    var subPerms = permute_Taylor_Hakes(arr.slice(0, i).concat(arr.slice(i + 1)));_x000D_
    for (var j = 0; j < subPerms.length; j++) {_x000D_
      subPerms[j].unshift(arr[i]);_x000D_
      permutations.push(subPerms[j]);_x000D_
    }_x000D_
  }_x000D_
  return permutations;_x000D_
}_x000D_
_x000D_
var Combinatorics = (function () {_x000D_
    'use strict';_x000D_
    var version = "0.5.2";_x000D_
    /* combinatory arithmetics */_x000D_
    var P = function(m, n) {_x000D_
        var p = 1;_x000D_
        while (n--) p *= m--;_x000D_
        return p;_x000D_
    };_x000D_
    var C = function(m, n) {_x000D_
        if (n > m) {_x000D_
            return 0;_x000D_
        }_x000D_
        return P(m, n) / P(n, n);_x000D_
    };_x000D_
    var factorial = function(n) {_x000D_
        return P(n, n);_x000D_
    };_x000D_
    var factoradic = function(n, d) {_x000D_
        var f = 1;_x000D_
        if (!d) {_x000D_
            for (d = 1; f < n; f *= ++d);_x000D_
            if (f > n) f /= d--;_x000D_
        } else {_x000D_
            f = factorial(d);_x000D_
        }_x000D_
        var result = [0];_x000D_
        for (; d; f /= d--) {_x000D_
            result[d] = Math.floor(n / f);_x000D_
            n %= f;_x000D_
        }_x000D_
        return result;_x000D_
    };_x000D_
    /* common methods */_x000D_
    var addProperties = function(dst, src) {_x000D_
        Object.keys(src).forEach(function(p) {_x000D_
            Object.defineProperty(dst, p, {_x000D_
                value: src[p],_x000D_
                configurable: p == 'next'_x000D_
            });_x000D_
        });_x000D_
    };_x000D_
    var hideProperty = function(o, p) {_x000D_
        Object.defineProperty(o, p, {_x000D_
            writable: true_x000D_
        });_x000D_
    };_x000D_
    var toArray = function(f) {_x000D_
        var e, result = [];_x000D_
        this.init();_x000D_
        while (e = this.next()) result.push(f ? f(e) : e);_x000D_
        this.init();_x000D_
        return result;_x000D_
    };_x000D_
    var common = {_x000D_
        toArray: toArray,_x000D_
        map: toArray,_x000D_
        forEach: function(f) {_x000D_
            var e;_x000D_
            this.init();_x000D_
            while (e = this.next()) f(e);_x000D_
            this.init();_x000D_
        },_x000D_
        filter: function(f) {_x000D_
            var e, result = [];_x000D_
            this.init();_x000D_
            while (e = this.next()) if (f(e)) result.push(e);_x000D_
            this.init();_x000D_
            return result;_x000D_
        },_x000D_
        lazyMap: function(f) {_x000D_
            this._lazyMap = f;_x000D_
            return this;_x000D_
        },_x000D_
        lazyFilter: function(f) {_x000D_
            Object.defineProperty(this, 'next', {_x000D_
                writable: true_x000D_
            });_x000D_
            if (typeof f !== 'function') {_x000D_
                this.next = this._next;_x000D_
            } else {_x000D_
                if (typeof (this._next) !== 'function') {_x000D_
                    this._next = this.next;_x000D_
                }_x000D_
                var _next = this._next.bind(this);_x000D_
                this.next = (function() {_x000D_
                    var e;_x000D_
                    while (e = _next()) {_x000D_
                        if (f(e))_x000D_
                            return e;_x000D_
                    }_x000D_
                    return e;_x000D_
                }).bind(this);_x000D_
            }_x000D_
            Object.defineProperty(this, 'next', {_x000D_
                writable: false_x000D_
            });_x000D_
            return this;_x000D_
        }_x000D_
_x000D_
    };_x000D_
    /* power set */_x000D_
    var power = function(ary, fun) {_x000D_
        var size = 1 << ary.length,_x000D_
            sizeOf = function() {_x000D_
                return size;_x000D_
            },_x000D_
            that = Object.create(ary.slice(), {_x000D_
                length: {_x000D_
                    get: sizeOf_x000D_
                }_x000D_
            });_x000D_
        hideProperty(that, 'index');_x000D_
        addProperties(that, {_x000D_
            valueOf: sizeOf,_x000D_
            init: function() {_x000D_
                that.index = 0;_x000D_
            },_x000D_
            nth: function(n) {_x000D_
                if (n >= size) return;_x000D_
                var i = 0,_x000D_
                    result = [];_x000D_
                for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);_x000D_
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;_x000D_
            },_x000D_
            next: function() {_x000D_
                return this.nth(this.index++);_x000D_
            }_x000D_
        });_x000D_
        addProperties(that, common);_x000D_
        that.init();_x000D_
        return (typeof (fun) === 'function') ? that.map(fun) : that;_x000D_
    };_x000D_
    /* combination */_x000D_
    var nextIndex = function(n) {_x000D_
        var smallest = n & -n,_x000D_
            ripple = n + smallest,_x000D_
            new_smallest = ripple & -ripple,_x000D_
            ones = ((new_smallest / smallest) >> 1) - 1;_x000D_
        return ripple | ones;_x000D_
    };_x000D_
    var combination = function(ary, nelem, fun) {_x000D_
        if (!nelem) nelem = ary.length;_x000D_
        if (nelem < 1) throw new RangeError;_x000D_
        if (nelem > ary.length) throw new RangeError;_x000D_
        var first = (1 << nelem) - 1,_x000D_
            size = C(ary.length, nelem),_x000D_
            maxIndex = 1 << ary.length,_x000D_
            sizeOf = function() {_x000D_
                return size;_x000D_
            },_x000D_
            that = Object.create(ary.slice(), {_x000D_
                length: {_x000D_
                    get: sizeOf_x000D_
                }_x000D_
            });_x000D_
        hideProperty(that, 'index');_x000D_
        addProperties(that, {_x000D_
            valueOf: sizeOf,_x000D_
            init: function() {_x000D_
                this.index = first;_x000D_
            },_x000D_
            next: function() {_x000D_
                if (this.index >= maxIndex) return;_x000D_
                var i = 0,_x000D_
                    n = this.index,_x000D_
                    result = [];_x000D_
                for (; n; n >>>= 1, i++) {_x000D_
                    if (n & 1) result[result.length] = this[i];_x000D_
                }_x000D_
_x000D_
                this.index = nextIndex(this.index);_x000D_
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;_x000D_
            }_x000D_
        });_x000D_
        addProperties(that, common);_x000D_
        that.init();_x000D_
        return (typeof (fun) === 'function') ? that.map(fun) : that;_x000D_
    };_x000D_
    /* permutation */_x000D_
    var _permutation = function(ary) {_x000D_
        var that = ary.slice(),_x000D_
            size = factorial(that.length);_x000D_
        that.index = 0;_x000D_
        that.next = function() {_x000D_
            if (this.index >= size) return;_x000D_
            var copy = this.slice(),_x000D_
                digits = factoradic(this.index, this.length),_x000D_
                result = [],_x000D_
                i = this.length - 1;_x000D_
            for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);_x000D_
            this.index++;_x000D_
            return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;_x000D_
        };_x000D_
        return that;_x000D_
    };_x000D_
    // which is really a permutation of combination_x000D_
    var permutation = function(ary, nelem, fun) {_x000D_
        if (!nelem) nelem = ary.length;_x000D_
        if (nelem < 1) throw new RangeError;_x000D_
        if (nelem > ary.length) throw new RangeError;_x000D_
        var size = P(ary.length, nelem),_x000D_
            sizeOf = function() {_x000D_
                return size;_x000D_
            },_x000D_
            that = Object.create(ary.slice(), {_x000D_
                length: {_x000D_
                    get: sizeOf_x000D_
                }_x000D_
            });_x000D_
        hideProperty(that, 'cmb');_x000D_
        hideProperty(that, 'per');_x000D_
        addProperties(that, {_x000D_
            valueOf: function() {_x000D_
                return size;_x000D_
            },_x000D_
            init: function() {_x000D_
                this.cmb = combination(ary, nelem);_x000D_
                this.per = _permutation(this.cmb.next());_x000D_
            },_x000D_
            next: function() {_x000D_
                var result = this.per.next();_x000D_
                if (!result) {_x000D_
                    var cmb = this.cmb.next();_x000D_
                    if (!cmb) return;_x000D_
                    this.per = _permutation(cmb);_x000D_
                    return this.next();_x000D_
                }_x000D_
                return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;_x000D_
            }_x000D_
        });_x000D_
        addProperties(that, common);_x000D_
        that.init();_x000D_
        return (typeof (fun) === 'function') ? that.map(fun) : that;_x000D_
    };_x000D_
_x000D_
    /* export */_x000D_
    var Combinatorics = Object.create(null);_x000D_
    addProperties(Combinatorics, {_x000D_
        C: C,_x000D_
        P: P,_x000D_
        factorial: factorial,_x000D_
        factoradic: factoradic,_x000D_
        permutation: permutation,_x000D_
    });_x000D_
    return Combinatorics;_x000D_
})();_x000D_
_x000D_
function permute_Technicalbloke(inputArray) {_x000D_
  if (inputArray.length === 1) return inputArray;_x000D_
  return inputArray.reduce( function(accumulator,_,index){_x000D_
    permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])_x000D_
    .map(value=>accumulator.push([inputArray[index],value]));_x000D_
    return accumulator;_x000D_
  },[]);_x000D_
}_x000D_
_x000D_
var suite = new Benchmark.Suite;_x000D_
var input = [0, 1, 2, 3, 4];_x000D_
_x000D_
suite.add('permute_SiGanteng', function() {_x000D_
    permute_SiGanteng(input);_x000D_
  })_x000D_
  .add('permute_delimited', function() {_x000D_
    permute_delimited(input);_x000D_
  })_x000D_
  .add('permute_monkey', function() {_x000D_
    permute_monkey(input);_x000D_
  })_x000D_
  .add('permute_Oriol', function() {_x000D_
    permute_Oriol(input);_x000D_
  })_x000D_
  .add('permute_MarkusT', function() {_x000D_
    permute_MarkusT(input);_x000D_
  })_x000D_
  .add('permute_le_m', function() {_x000D_
    permute_le_m(input);_x000D_
  })_x000D_
  .add('permute_Urielzen', function() {_x000D_
    permute_Urielzen(input);_x000D_
  })_x000D_
  .add('permute_Taylor_Hakes', function() {_x000D_
    permute_Taylor_Hakes(input);_x000D_
  })_x000D_
  .add('permute_Combinatorics', function() {_x000D_
    Combinatorics.permutation(input).toArray();_x000D_
  })_x000D_
  .add('permute_Technicalbloke', function() {_x000D_
    permute_Technicalbloke(input);_x000D_
  })_x000D_
  .on('cycle', function(event) {_x000D_
    console.log(String(event.target));_x000D_
  })_x000D_
  .on('complete', function() {_x000D_
    console.log('Fastest is ' + this.filter('fastest').map('name'));_x000D_
  })_x000D_
  .run({async: true});

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>_x000D_
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>_x000D_
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Run-time results for Chrome 48:

•   99.152ms This algorithm
•  153.115ms MarkusT
•  401.255ms js-combinatorics
•  497.037ms Urielzen
•  925.669ms Oriol
• 1026.571ms SiGanteng
• 2529.841ms delimited
• 3992.622ms monkey
• 4514.665ms Oriol

I used a string instead of an array and it seems like my algorithm consumes very less time. I am posting my algorithm here, am I measuring the time correctly?

console.time('process');

var result = []

function swapper(toSwap){
    let start = toSwap[0]
    let end = toSwap.slice(1)
    return end + start
}


function perm(str){
    let i = str.length
    let filling = i - 1

    let buckets = i*filling
    let tmpSwap = ''
    for(let j=0; j<filling; j++){
        if(j===0){
            result.push(str)
        }else{
          if(j === 1){
              tmpSwap = swapper(str.slice(1))
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }

          }else{
              tmpSwap = swapper(tmpSwap)
              result.push(str[0]+ tmpSwap)
              if(j === filling-1 && result.length < buckets){
                  perm(swapper(str))
              }
          }
        }
    }

    if(result.length = buckets){
      return result
    }else{
      return 'something went wrong'
    }

}





console.log(perm('abcdefghijk'))

console.timeEnd('process');

Here's a cool solution

const rotations = ([l, ...ls], right=[]) =>_x000D_
  l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []_x000D_
_x000D_
const permutations = ([x, ...xs]) =>_x000D_
  x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]_x000D_
  _x000D_
console.log(permutations("cat"))

Here's one I made...

const permute = (ar) =>
  ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
    {permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);

And here it is again but written less tersely!...

function permute(inputArray) {
  if (inputArray.length === 1) return inputArray;
  return inputArray.reduce( function(accumulator,_,index){
    permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
      .map(value=>accumulator.push([].concat(inputArray[index],value)));
    return accumulator;
  },[]);
}

How it works: If the array is longer than one element it steps through each element and concatenates it with a recursive call to itself with the remaining elements as it's argument. It doesn't mutate the original array.

I wrote a post to demonstrate how to permute an array in JavaScript. Here is the code which does this.

var count=0;
function permute(pre,cur){ 
    var len=cur.length;
    for(var i=0;i<len;i++){
        var p=clone(pre);
        var c=clone(cur);
        p.push(cur[i]);
        remove(c,cur[i]);
        if(len>1){
            permute(p,c);
        }else{
            print(p);
            count++;
        }
    }
}
function print(arr){
    var len=arr.length;
    for(var i=0;i<len;i++){
        document.write(arr[i]+" ");
    }
    document.write("<br />");
}
function remove(arr,item){
    if(contains(arr,item)){
        var len=arr.length;
        for(var i = len-1; i >= 0; i--){ // STEP 1
            if(arr[i] == item){             // STEP 2
                arr.splice(i,1);              // STEP 3
            }
        }
    }
}
function contains(arr,value){
    for(var i=0;i<arr.length;i++){
        if(arr[i]==value){
            return true;
        }
    }
    return false;
}
function clone(arr){
    var a=new Array();
    var len=arr.length;
    for(var i=0;i<len;i++){
        a.push(arr[i]);
    }
    return a;
}

Just call

permute([], [1,2,3,4])

will work. For details on how this works, please refer to the explanation in that post.

Most answers to this question use expensive operations like continuous insertions and deletions of items in an array, or copying arrays reiteratively.

Instead, this is the typical backtracking solution:

function permute(arr) {
  var results = [],
      l = arr.length,
      used = Array(l), // Array of bools. Keeps track of used items
      data = Array(l); // Stores items of the current permutation
  (function backtracking(pos) {
    if(pos == l) return results.push(data.slice());
    for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
      used[i] = true;      // Mark item as used
      data[pos] = arr[i];  // Assign item at the current position
      backtracking(pos+1); // Recursive call
      used[i] = false;     // Mark item as not used
    }
  })(0);
  return results;
}

permute([1,2,3,4]); // [  [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1]  ]

Since the results array will be huge, it might be a good idea to iterate the results one by one instead of allocating all the data simultaneously. In ES6, this can be done with generators:

function permute(arr) {
  var l = arr.length,
      used = Array(l),
      data = Array(l);
  return function* backtracking(pos) {
    if(pos == l) yield data.slice();
    else for(var i=0; i<l; ++i) if(!used[i]) {
      used[i] = true;
      data[pos] = arr[i];
      yield* backtracking(pos+1);
      used[i] = false;
    }
  }(0);
}

var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}

function nPr(xs, r) {
    if (!r) return [];
    return xs.reduce(function(memo, cur, i) {
        var others  = xs.slice(0,i).concat(xs.slice(i+1)),
            perms   = nPr(others, r-1),
            newElms = !perms.length ? [[cur]] :
                      perms.map(function(perm) { return [cur].concat(perm) });
        return memo.concat(newElms);
    }, []);
}

Most of the other answers do not utilize the new javascript generator functions which is a perfect solution to this type of problem. You probably only need one permutation at time in memory. Also, I prefer to generate a permutation of a range of indices as this allows me to index each permutation and jump straight to any particular permutation as well as be used to permutate any other collection.

// ES6 generator version of python itertools [permutations and combinations]_x000D_
const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; }_x000D_
const isEmpty = arr => arr.length === 0;_x000D_
_x000D_
const permutations = function*(a) {_x000D_
    const r = arguments[1] || [];_x000D_
    if (isEmpty(a)) yield r;_x000D_
    for (let i of range(a.length)) {_x000D_
        const aa = [...a];_x000D_
        const rr = [...r, ...aa.splice(i, 1)];_x000D_
        yield* permutations(aa, rr);_x000D_
    }_x000D_
}_x000D_
console.log('permutations of ABC');_x000D_
console.log(JSON.stringify([...permutations([...'ABC'])]));_x000D_
_x000D_
const combinations = function*(a, count) {_x000D_
    const r = arguments[2] || [];_x000D_
    if (count) {_x000D_
        count = count - 1;_x000D_
        for (let i of range(a.length - count)) {_x000D_
            const aa = a.slice(i);_x000D_
            const rr = [...r, ...aa.splice(0, 1)];_x000D_
            yield* combinations(aa, count, rr);_x000D_
        }_x000D_
    } else {_x000D_
        yield r;_x000D_
    }_x000D_
}_x000D_
console.log('combinations of 2 of ABC');_x000D_
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));_x000D_
_x000D_
_x000D_
_x000D_
const permutator = function() {_x000D_
    const range = function*(args) {_x000D_
        let {begin = 0, count} = args;_x000D_
        for (let i = begin; count; count--, i+=1) {_x000D_
            yield i;_x000D_
        }_x000D_
    }_x000D_
    const factorial = fact => fact ? fact * factorial(fact - 1) : 1;_x000D_
_x000D_
    return {_x000D_
        perm: function(n, permutationId) {_x000D_
            const indexCount = factorial(n);_x000D_
            permutationId = ((permutationId%indexCount)+indexCount)%indexCount;_x000D_
_x000D_
            let permutation = [0];_x000D_
            for (const choiceCount of range({begin: 2, count: n-1})) {_x000D_
                const choice = permutationId % choiceCount;_x000D_
                const lastIndex = permutation.length;_x000D_
_x000D_
                permutation.push(choice);_x000D_
                permutation = permutation.map((cv, i, orig) => _x000D_
                    (cv < choice || i == lastIndex) ? cv : cv + 1_x000D_
                );_x000D_
_x000D_
                permutationId = Math.floor(permutationId / choiceCount);_x000D_
            }_x000D_
            return permutation.reverse();_x000D_
        },_x000D_
        perms: function*(n) {_x000D_
            for (let i of range({count: factorial(n)})) {_x000D_
                yield this.perm(n, i);_x000D_
            }_x000D_
        }_x000D_
    };_x000D_
}();_x000D_
_x000D_
console.log('indexing type permutator');_x000D_
let i = 0;_x000D_
for (let elem of permutator.perms(3)) {_x000D_
  console.log(`${i}: ${elem}`);_x000D_
  i+=1;_x000D_
}_x000D_
console.log();_x000D_
console.log(`3: ${permutator.perm(3,3)}`);

I had a crack at making a version of this that attempts to be concise yet readable, and purely functional programming.

function stringPermutations ([...input]) {
  if (input.length === 1) return input;

  return input
    .map((thisChar, index) => {
      const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
      return stringPermutations(remainingChars)
        .map(remainder => thisChar + remainder);
    })
    .reduce((acc, cur) => [...acc, ...cur]);
}

Note that the argument formatting turns an input string into an array. Not sure if that's a bit too magical.. Not sure I've seen it in the wild. For real readability I'd probably instead do input = [...input] for the first line of the function.

Here is a minimal ES6 version. The flatten and without functions can be pulled from Lodash.

const flatten = xs =>
    xs.reduce((cum, next) => [...cum, ...next], []);

const without = (xs, x) =>
    xs.filter(y => y !== x);

const permutations = xs =>
    flatten(xs.map(x =>
        xs.length < 2
            ? [xs]
            : permutations(without(xs, x)).map(perm => [x, ...perm])
    ));

Result:

permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

function swap(array1, index1, index2) {
    var temp;
    temp = array1[index1];
    array1[index1] = array1[index2];
    array1[index2] = temp;
}

function permute(a, l, r) {
    var i;
    if (l == r) {
        console.log(a.join(''));
    } else {
        for (i = l; i <= r; i++) {
            swap(a, l, i);
            permute(a, l + 1, r);
            swap(a, l, i);
        }
    }
}


permute(["A","B","C", "D"],0,3);

// sample execution //for more details refer this link

// http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

   function perm(xs) {
       return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
        for (var i = 0; i < xs.length; i++) {
          acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
        }
        return acc;
      }, []);
    }

Test it with:

console.log(JSON.stringify(perm([1, 2, 3,4])));

This is a very nice use-case for map/reduce:

function permutations(arr) {
    return (arr.length === 1) ? arr :
    arr.reduce((acc, cv, index) => {
        let remaining = [...arr];
        remaining.splice(index, 1);
        return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
    }, []);
}

• First, we handle the base case and simply return the array if there is only on item in it
• In all other cases
  • we create an empty array
  • loop over the input-array
  • and add an array of the current value and all permutations of the remaining array [].concat(cv,a)

My first contribution to the site. Also, according to the tests that I have done, this code runs faster than all the other methods mentioned here before this date, of course it is minimal if there are few values, but the time increases exponentially when adding too many.

var result = permutations([1,2,3,4]);

var output = window.document.getElementById('output');
output.innerHTML = JSON.stringify(result);

function permutations(arr) {
    var finalArr = [];
    function iterator(arrayTaken, tree) {
        var temp;
        for (var i = 0; i < tree; i++) {
            temp = arrayTaken.slice();
            temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
            if (tree >= arr.length) {
                finalArr.push(temp);
            } else {
                iterator(temp, tree + 1);
            }
        }
    }
    iterator(arr, 1);
    return finalArr;
};

<div id="output"></div>

The following function permutates an array of any type and calls a specified callback function on each permutation found:

/*
  Permutate the elements in the specified array by swapping them
  in-place and calling the specified callback function on the array
  for each permutation.

  Return the number of permutations.

  If array is undefined, null or empty, return 0.

  NOTE: when permutation succeeds, the array should be in the original state
  on exit!
*/
  function permutate(array, callback) {
    // Do the actual permuation work on array[], starting at index
    function p(array, index, callback) {
      // Swap elements i1 and i2 in array a[]
      function swap(a, i1, i2) {
        var t = a[i1];
        a[i1] = a[i2];
        a[i2] = t;
      }

      if (index == array.length - 1) {
        callback(array);
        return 1;
      } else {
        var count = p(array, index + 1, callback);
        for (var i = index + 1; i < array.length; i++) {
          swap(array, i, index);
          count += p(array, index + 1, callback);
          swap(array, i, index);
        }
        return count;
      }
    }

    if (!array || array.length == 0) {
      return 0;
    }
    return p(array, 0, callback);
  }

If you call it like this:

  // Empty array to hold results
  var result = [];
  // Permutate [1, 2, 3], pushing every permutation onto result[]
  permutate([1, 2, 3], function (a) {
    // Create a copy of a[] and add that to result[]
    result.push(a.slice(0));
  });
  // Show result[]
  document.write(result);

I think it will do exactly what you need - fill an array called result with the permutations of the array [1, 2, 3]. The result is:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

Slightly clearer code on JSFiddle: http://jsfiddle.net/MgmMg/6/

Here's a very concise and recursive solution that allows you to input the size of the output permutations similar to the statistical operator nPr. "5 permutation 3". This allows you to get all possible permutations with a specific size.

function generatePermutations(list, size=list.length) {
    if (size > list.length) return [];
    else if (size == 1) return list.map(d=>[d]); 
    return list.flatMap(d => generatePermutations(list.filter(a => a !== d), size - 1).map(item => [d, ...item]));
}

generatePermutations([1,2,3])

[[1, 2, 3],[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

generatePermutations([1,2,3],2)

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Fastest, most (resorces) effective and most elegant version nowadays (2020)

function getArrayMutations (arr, perms = [], len = arr.length) {
  if (len === 1) perms.push(arr.slice(0))

  for (let i = 0; i < len; i++) {
    getArrayMutations(arr, perms, len - 1)

    len % 2 // parity dependent adjacent elements swap
      ? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
      : [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
  }

  return perms
}

const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9]

const startTime = performance.now()
const arrayOfMutations = getArrayMutations(arrayToMutate)
const stopTime = performance.now()
const duration = (stopTime - startTime) / 1000

console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)

const removeItem = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i+1));
}

const makePermutations = (strArr) => {
  const doPermutation = (strArr, pairArr) => {
    return strArr.reduce((result, permutItem, i) => {
      const currentPair = removeItem(pairArr, i);
      const tempResult = currentPair.map((item) => permutItem+item);
      return tempResult.length === 1 ? result.concat(tempResult) :
             result.concat(doPermutation(tempResult, currentPair));
    }, []);
  }
  return strArr.length === 1 ? strArr :
         doPermutation(strArr, strArr);
}


makePermutations(["a", "b", "c", "d"]);
//result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]

var inputArray = [1, 2, 3];

var result = inputArray.reduce(function permute(res, item, key, arr) {
    return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);


alert(JSON.stringify(result));

Little late, but like to add a slightly more elegant version here. Can be any array...

function permutator(inputArr) {
  var results = [];

  function permute(arr, memo) {
    var cur, memo = memo || [];

    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }

    return results;
  }

  return permute(inputArr);
}

Adding an ES6 (2015) version. Also does not mutate the original input array. Works in the console in Chrome...

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }

 permute(inputArr)

 return result;
}

So...

permutator(['c','a','t']);

Yields...

[ [ 'c', 'a', 't' ],
  [ 'c', 't', 'a' ],
  [ 'a', 'c', 't' ],
  [ 'a', 't', 'c' ],
  [ 't', 'c', 'a' ],
  [ 't', 'a', 'c' ] ]

And...

permutator([1,2,3]);

Yields...

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]