javascript - 反向排列指数

Question

我编写了一个函数，用于根据索引计算数组 [a,b,c,...] 的排列，例如:

0 -> a b c 
1 -> a c b 
2 -> b a c
3 -> b c a
4 -> c a b
5 -> c b a     

通过这个递归函数:

function factorial(n) { return n <= 1 ? 1 : n*factorial(n-1); }
function permutation(ar, n) {
   if (ar.length == 1) return [ar[0]]; 
   var x = factorial(ar.length-1);  // get first element
   return ar.splice(Math.floor(n/x),1).concat( permutation( ar, n % x ) )
}

现在我正在寻找一个函数，该函数采用排列的索引来获取反向排列的索引，即

    index    perm    reversed  reversed index
    **0** -> a b c -> c b a -> **5**
    **1** -> a c b -> b c a -> **3**
    **2** -> b a c -> c a b -> **4**
    **3** -> b c a -> a c b -> **1**
    **4** -> c a b -> b a c -> **2**
    **5** -> c b a -> a b c -> **0**

我可以计算所有排列，计算它们的反向排列并建立它的索引，但似乎应该有一种数学方法可以在不计算它的情况下获得反向排列的索引。

Answer 1

如果您查看您的排列，您会发现它的结构如下:(长度 = 3 的示例)

首先，您的排列被分成 3 组，每组包含 2 个!元素然后将这些子组分成 2 组，长度为 1! , 之后子子组不再划分。

所以实际上你的排列可以通过首先说明它在哪个子组中然后说明它在哪个子子组中来“查找”...

例如排列 2:'bac' 在子组 1(从 0 开始)和子组 0 中。

所以我们可以说 2 = (1,0)，如 3 = 1*(2!)+0*(1!)4 则为 (2,0)现在如果我们将 2 翻转为 (0,1) 并向其添加 4,(2,0) 我们将得到 (2,1)这对所有排列都是正确的

本质上:(n = 排列长度)

把你的索引写成a*(n-1)! + b*(n-2)! + ... + z*(1!) ( a = floor(index/(n-1)), b = floor ((index%(n-1))/(n-2)!) , ... )

找到一个数字，如果你翻转最小的一个并将它们加在一起，你会得到 (n-1,n-2,n-3,...,1)

可能有一个有效的算法可以做到这一点。