Permutations without recursive function call

I think this post should help you. The algorithm should be easily translatable to JavaScript (I think it is more than 70% already JavaScript-compatible).

slice and reverse are bad calls to use if you are after efficiency. The algorithm described in the post is following the most efficient implementation of the next_permutation function, that is even integrated in some programming languages (like C++ e.g.)

EDIT

As I iterated over the algorithm once again I think you can just remove the types of the variables and you should be good to go in JavaScript.

EDIT

JavaScript version:

function nextPermutation(array) {
    // Find non-increasing suffix
    var i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i])
        i--;
    if (i <= 0)
        return false;

    // Find successor to pivot
    var j = array.length - 1;
    while (array[j] <= array[i - 1])
        j--;
    var temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
    return true;
}

Here is a simple solution to compute the nth permutation of a string:

function string_nth_permutation(str, n) {
    var len = str.length, i, f, res;

    for (f = i = 1; i <= len; i++)
        f *= i;

    if (n >= 0 && n < f) {
        for (res = ""; len > 0; len--) {
            f /= len;
            i = Math.floor(n / f);
            n %= f;
            res += str.charAt(i);
            str = str.substring(0, i) + str.substring(i + 1);
        }
    }
    return res;
}

The algorithm follows these simple steps:

• first compute f = len!, there are factorial(len) total permutations of a set of len different elements.
• as the first element, divide the permutation number by (len-1)! and chose the element at the resulting offset. There are (len-1)! different permutations that have any given element as their first element.
• remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
• perform these steps with the rest of the set, whose length is reduced by one.

This algorithm is very simple and has interesting properties:

• It computes the n-th permutation directly.
• If the set is ordered, the permutations are generated in lexicographical order.
• It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
• Permutation number 0 is the set in the order given.
• Permutation number factorial(a.length)-1 is the last one: the set a in reverse order.
• Permutations outside this range are returned as undefined.

It can easily be converted to handle a set stored as an array:

function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}

clarification:

• f is first computed as factorial(len).
• For each step, f is divided by len, giving exacty the previous factorial.
• n divided by this new value of f gives the slot number among the len slots that have the same initial element. Javascript does not have integral division, we could use (n / f) ... 0) to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements. Math.floor(n / f) allows for sets of up to 18 elements. We could also use (n - n % f) / f, probably more efficient too.
• n must be reduced to the permutation number within this slot, that is the remainder of the division n / f.

We could use i differently in the second loop, storing the division remainder, avoiding Math.floor() and the extra % operator. Here is an alternative for this loop that may be even less readable:

        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            i = n % (f /= len);
            res.push(b.splice((n - i) / f, 1)[0]);
            n = i;
        }