14

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 ?

Kamil Kiełczewski
  • 85,173
  • 29
  • 368
  • 345
Harry
  • 183
  • 1
  • 8
  • Use a counter variable, and return when the counter reaches `i`. – Barmar Nov 05 '16 at 18:14
  • Is arr filled with arbitrary values or with something like 1..n? – MBo Nov 05 '16 at 18:19
  • 1
    Well, I know you guys don't like this kind of suggestion, but have you considered googling? E.g. you might find [ŧhis](https://en.wikipedia.org/wiki/Permutation#Numbering_permutations). –  Nov 05 '16 at 18:22

3 Answers3

34

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; }
Emma
  • 27,428
  • 11
  • 44
  • 69
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
4

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(' '));
}
rrk
  • 15,677
  • 4
  • 29
  • 45
TTCUSM
  • 62
  • 2
  • Edited my code so that it searches for used elements at the end of the array in addition to the beginning. – TTCUSM Nov 19 '16 at 11:21
4

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() );
Kamil Kiełczewski
  • 85,173
  • 29
  • 368
  • 345