Find ith permutation in javascript

Question

Given an array arr of size n, and and index 0<=i<n! I want to return the i'th permutation.

I was able to write a method that gets all permutations:

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

  for (var i = 0; i <  arr.length; i++) { 
    var subPerms = permute(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;
}

How do I trim it to get only one branch of the recursion ?

Answer 1

You could use the factorial of the array length as helper for getting the target permutation. Basically, this algorithm calculates the array indices upon which reassembles the result.

function getN(n, array) {
    var f,
        l = array.length,
        indices = [];

    array = array.slice();
    while (l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n %= f;
    }
    return indices.map(function (i) {
        return array.splice(i, 1)[0];
    });
}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l,
    array = [1, 2, 3, 4];

for (i = 0, l = factorial(array.length); i < l; i++) {
    console.log(i, '>', getN(i, array).join(' '));
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

Here's the less computationally expensive answer: keep track of the used elements using an array of boolean flags. It may not seem like much of an improvement, since you still have to scan the array of flags to get the element you're looking for, resulting in O(N^2) performance. However, you may get some improvement if you take advantage of the layout of elements within the array:

function getN(n, array) {
    var f,
        l = array.length,
        indices = [];

    //Instead of using splice() to remove elements that are
    //already in the permutation, I'll use an array of bit flags
    //to track used elements.
    var indexMask = [];
    indexMask.length = array.length;
    var indexMaskInit = 0;
    for(indexMaskInit = 0; indexMaskInit < indexMask.length;
            indexMaskInit++)    {
        indexMask[indexMaskInit] = true;
    }

    array = array.slice();
    while(l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n %= f;
    }

    var toReturn = [];
    toReturn.length = array.length;
    //Now, extract the elements using the array of indices.
    var numUsed;
    for(numUsed = 0; numUsed < indices.length; numUsed++)   {
        //factIndex is the index in the set of elements that have
        //not been selected yet.
        var factIndex = indices[numUsed];
        var elementFound = false;
        //This code searches for the element by assuming that some
        //elements have already been selected.  The number of used
        //elements can be found using the index of the outer loop.
        //By counting the number of used elements at the beginning
        //of the array, it may be possible to calculate an offset
        //that can be used to find the desired element.
        if(factIndex > 2 * numUsed)
        {
            var offset = 0, scanIndex;
            //Boundary condition:  no elements have been used yet,
            //in which case we can use factIndex directly.
            if(numUsed === 0)   {
                elementFound = true;
            }
            else    {
                //Loop to 2*numUsed, to avoid a linear search.
                for(scanIndex = 0; scanIndex < 2 * numUsed;
                        scanIndex++)    {
                    if(!indexMask[scanIndex])   {
                        offset++;
                    }
                    //Boundary condition:  all used elements have
                    //been found.
                    if(offset >= numUsed)   {
                        elementFound = true;
                        break;
                    }
                }
            }
            if(elementFound)    {
                factIndex += offset;
            }
        }
        //This code starts at the end of the array and counts the
        //number of used elements.
        else if ((indices.length - 1 - factIndex) > 2 * numUsed)    {
            var offset = 0, scanIndex;
            //Boundary condition:  no elements have been used yet,
            //in which case we can use factIndex directly.
            if(numUsed === 0)   {
                elementFound = true;
            }
            else    {
                var n = indices.length - 1;
                //Loop to 2*numUsed, to avoid a linear search.
                for(scanIndex = n; scanIndex > n - 2 * numUsed;
                        scanIndex--)    {
                    if(!indexMask[scanIndex])   {
                        offset++;
                    }
                    //Boundary condition:  all used elements have
                    //been found.
                    if(offset >= numUsed)   {
                        elementFound = true;
                        break;
                    }
                }
            }
            if(elementFound)    {
                factIndex += (numUsed - offset);
            }
        }
        //If the number of used elements is not much greater than
        //factIndex, or they do not all cluster at the beginning
        //of the array, it may be better to run a linear search.
        if(!elementFound)
        {
            var searchIndex = 0, i;
            for(i = 0; i < indexMask.length; i++)   {
                if(indexMask[i])    {
                    if(searchIndex >= factIndex)    {
                        break;
                    }
                    else    {
                        searchIndex++;
                    }
                }
            }
            factIndex = i;
        }
        toReturn[numUsed] = array[factIndex];
        indexMask[factIndex] = false;
    }
    return toReturn;
}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l;
var array = [1, 2, 3, 4];
//var array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];

for (i = 0, l = factorial(array.length); i < l; i++) {
    console.log(i, getN(i, array).join(' '));
}

Answer 3

Try (algorithm from here)

function perm(n,arr) {
    let r=[],i=1;
    while (n) { r.unshift(n%i); n=n/i++|0 }
    let s= i-1 ? arr.splice(-r.length) : arr;    
    return arr.concat(r.map( x=> s.splice(x,1)[0] ));
}

// TEST
for(let i=0; i<4*3*2*1; i++) console.log( i, perm(i,[1,2,3,4]).join() );