Unrank a permutation rank (https://doi.org/10.3390/a14030097)

unrank.js

// Cyann Donnot, Antoine Genitrini, Yassine Herida. Unranking Combinations Lexicographically: an
// efficient new strategy compared with others. 2020. hal-02462764
// https://hal.sorbonne-universite.fr/hal-02462764v1/preview/paper.pdf

const crypto = require("crypto");

function randomBigInt(bitLength) {
  const u = crypto.randomBytes(bitLength / 8);
  return BigInt("0x" + u.toString("hex"));
}

function range(n) {
  const arr = Array(n).fill();
  return arr.map((_, i) => i);
}

function factorial(n) {
  let result = 1n;
  for (let i = BigInt(n); i >= 2n; i--) result *= i;
  return result;
}

function factoradic(n, len) {
  let result = [];
  let radix = 1n;
  let quotient = BigInt(n);
  let remainder = 0n;

  while (quotient != 0n) {
    [quotient, remainder] = [quotient / radix, quotient % radix];
    result.push(Number(remainder));
    radix++;
  }

  if (len > result.length) {
    const zeros = Array(len - result.length).fill(0);
    result = [...result, ...zeros];
  }

  return result;
}

function unrank(rank, n) {
  const F = factoradic(rank, n);
  const identity = range(n);
  const pi = [];

  while (F.length) {
    const f = F.pop();
    pi.push(identity[f]);
    identity.splice(f, 1);
  }

  return pi;
}

const n = 100;
const m = factorial(n) - 1n;

const { length: bitLength } = m.toString(2);
const rank = randomBigInt(bitLength);
console.log(unrank(rank, n));