Javascript : 如何在排列后取回初始值

Question

从一个 6 位数的值（即“123456”）和一个 [0->9] table 开始，这个脚本（但许多其他存在......）产生 table :

  let tabl10 = [0,1,2,3,4,5,6,7,8,9],
      permut = permutation( 123456 , tabl10 )

  console.log(permut) // 0,4,1,6,5,9,2,3,7,8

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

   function factorial(n) {
       let r = 1;
       while (n) {
           r *= n;
           n--;
       }
       return r;
   }

我的问题是：是否可以从“0,4,1,6,5,9,2,3,7,8”排列中检索“123456”？

我们有 10 个！（362.88 万）种可能的排列并一一尝试所有排列，直到我们发现第 123456 种排列是痛苦的：可以探索所有排列并用 7 位 table [0,1,2 ,3,4,5,6]: 7!=5040，但 8 位数字 (40320) 或更高数字肯定会冻结浏览器。如何实现？

Answer 1

在一个Lehmer code的排列perm中，第i个数是i右边小于perm[i]的元素个数.因此，给定一个排列，您可以先计算它的 LC，然后将 LC 从阶乘系统转换为 int，从而为您提供排列的索引。

完整代码：

// int => LC
function int2lc(n, len) {
    let lc = []
    for (let i = 1; i <= len; i++) {
        lc[len - i] = (n % i)
        n = (n / i) | 0
    }
    return lc
}

// LC => int
function lc2int(lc, len) {
    let n = 0, f = 1
    for (let i = 1; i <= len; i++) {
        n += lc[len - i] * f
        f *= i
    }
    return n
}

// LC => permutation
function lc2perm(a, lc) {
    let perm = [], copy = [...a]
    for (let i = 0; i < lc.length; i++) {
        perm[i] = copy[lc[i]]
        copy.splice(lc[i], 1)
    }
    return perm
}

// permutation => LC
function perm2lc(perm) {
    let lc = []
    for (let i = 0; i < perm.length; i++) {
        let c = 0
        for (let k = i + 1; k < perm.length; k++)
            c += perm[k] < perm[i]
        lc[i] = c
    }
    return lc
}

//

A = [0,1,2,3,4,5,6,7,8,9]

// index to perm

N = 123456
lc = int2lc(N, A.length)
console.log('LEHMER', ...lc)
perm = lc2perm(A, lc)
console.log('PERMUT', ...perm)

// perm to index

lc2 = perm2lc(perm)
console.log('LEHMER', ...lc2)
M = lc2int(lc2, A.length)
console.log('INDEX ', M)

Javascript : 如何在排列后取回初始值

Javascript : How to retrieve initial value after permutation

javascript

permutation