Get the n-th permutation of a large set of elements

Question

I'd like to write a JavaScript program that arranges a set of 36 numbers in all possible permutations (10 permutations per second). There are 36 factorial ways to arrange these numbers.

I know that my program won't end until the end of the earth :) (that's exactly what I want to show).

It starts with the following sequence:

1. permutation: 0,1,2,3,4,5,6,...,32,33,34,35
2. permutation: 0,1,2,3,4,5,6,...,32,33,35,34
3. permutation: 0,1,2,3,4,5,6,...,32,34,33,35

..... (A LOT more permutations here)....

Is there a way to calculate the 5'595'000'000th (time in deciseconds since 01.01.2000) permutation without calculating all the previous ones? Calculate the previous ones would literally take forever!

Also, if I know the 5'595'000'000th permutation I need a way to calculate the next one.

All permutation algorithms I found calculate all permutations at once. Which is not an option with that many permutations.

Is this even possible or am I doomed?

Answer 1

Here are two functions:

• getPermutationByRank: gets a permutation (array) by its rank number. Inspiration taken from this answer;
• nextPermutation: mutates a given permutation to the next one in the order. Inspiration taken from this answer

That is basically what you need, but I have added a generator, which uses the above two functions to generate permutations from a certain rank onwards.

Finally a formatting function translates a given permutation to a character set (10 digits + 26 letters = 36 different characters).

The snippet calculates the current number of deci-seconds since 2000-01-01 and outputs the corresponding permutation, updating it to the next permutation every deci-second that passes:

// See https://stackoverflow.com/a/7919887/5459839
function getPermutationByRank(n, rank) {
    // Sageguard for inaccurate calculations: rank <= 9007199254740991
    if (rank > Number.MAX_SAFE_INTEGER) throw "Too large rank for JavaScript";
    var perm = (function loop(i, fact) {
        // Calculate factorials and subtract from rank from highest to lowest
        return i > n ? [] :
               [loop(i+1, fact * i).concat(Math.floor(rank / fact) % n),
                rank = rank % fact][0];
    })(1, 1);
    // Readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (let k = n - 1; k > 0; --k)
      for (let j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;
    return perm;
}

// See https://stackoverflow.com/a/1622539/5459839:
function nextPermutation(perm) {
    // Find longest non-increasing suffix
    var i = perm.length - 2;
    while (i >= 0 && perm[i] >= perm[i + 1])
        i--;
    // Now i is the head index of the suffix
    
    // Are we at the last permutation already?
    if (i < 0) return; // no more permuations
    
    // Let perm[i] be the pivot
    // Find rightmost element that exceeds the pivot
    var j = perm.length - 1;
    while (perm[j] <= perm[i])
        j--;
    // Now the value perm[j] will become the new pivot
    // Assertion: j >= i
    
    // Swap the pivot with j
    [perm[i], perm[j]] = [perm[j], perm[i]];
    
    // Reverse the suffix
    j = perm.length - 1;
    i++;
    while (i < j) {
        [perm[i], perm[j]] = [perm[j], perm[i]];
        i++;
        j--;
    }
    return perm;
}

// Create a generator using above two functions:
function* generatePermutationsFrom(n, rank) {
    var perm = getPermutationByRank(n, rank);

    yield perm;
    while (nextPermutation(perm)) {
        yield perm;
    }
}

// Utility functions for OP specific requirements
function deciSecondsSince(dt) {
    return Math.floor((Date.now() - dt.getTime())/100);
}

function permToString(perm) {
    var chars = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    return perm.map ( v => chars[v] ).join('');
}

var deciSecs = deciSecondsSince(new Date('2000-01-01')); // ~5293000000 
var iter = generatePermutationsFrom(36, deciSecs);

// Output next permuation every decisecond:
document.body.textContent = permToString(iter.next().value);
setInterval(function () {
    document.body.textContent = permToString(iter.next().value);
}, 100);

body { font-family: monospace }

Disclaimers:

1. this works for the rank numbers you ask about (like 5293000000), but if the rank exceeds the precision that JavaScript can offer, the results will be wrong. In fact, the factorials which are calculated in the first function are only precise up to 18!, after that they lose precision. This has no impact in the algorithm as long as your rank is within the range that JavaScript supports (roughly 16 digits). The first function therefore has a safeguard.

2. setInterval is not a very reliable way for keeping pace with time, so after a while the number iterations might get out of sync with the real number of deci-seconds that passed since the first iteration. But this seemed not that important for your purposes. If it is, then have a look at this answer to compensate for such drifting.