从映射到排列的数字,如何生成与先前的perm不同的其他排列.通过交换元素？

Question

使用Lehmer代码,可以使用因子数系统对N个元素序列的任何排列进行编码并映射到十进制数.

示例:

Lehmer代码ABCD排列:

ABDC => 0010
CBAD => 2100
DCBA => 3210

这些inversions vectors可以使用阶乘法转换为小数:

2100 => 2 x 3! + 1 x 2! + 0 x 1! + 0 x 0!
     => 2 x 6  + 1 x 2  + 0 x 1  + 0 x 1
     => 14

因此CBAD排列可以直接映射到数字14.

我的问题是:

从映射到置换的数字,是否有一种计算有效的方法通过交换序列中的两个元素来生成与先前的置换不同的其他排列的数量？

---

示例:我们有4个(映射到ADBC),我们想要交换前两个元素.结果是18(或DABC).

4    => 18
0200 => 3000
ADBC => DABC

方法将如下声明:

swap(4, 0, 1); //return 18

我想避免再次完成整个过程但反过来:

Number => Factorial => Rebuild original permutation and swap elements (costly) =>
  Factorial => Number

注意:在维基百科上有关于Steinhaus-Johnson-Trotter算法的文章, 但我不确定它会对此有所帮助.

Answer 1

（回答我自己的问题）

我终于发现了。我花了一段时间，但这是最终的公式：

int swap(int value, int indexA, int indexB)
{
   int valueA = value % factorial(indexA+1) / factorial(indexA);
   int valueB = value % factorial(indexB+1) / factorial(indexB);

   int deltaA = valueB - valueA;
   if (valueB >= valueA) deltaA++;

   int deltaB = valueA - valueB;
   if (valueA > valueB) deltaB--;

   return value + (deltaA * factorial(indexA)) + (deltaB * factorial(indexB));
}

//note: indexes have to be given from right to left
//so to swap elements at 0, 1 for 4 : swap(4, 3, 2); 

一些解释：

举个例子，我们以14. 阶乘表示为：

2 x 3! + 1 x 2! + 0 x 1! + 0 x 0!

如果我们想交换序列的前两个元素（CBAD=>BCAD或2100=> 1100），我们需要在阶乘中采用2和项，然后交换它们：1

1 x 3! + 2 x 2! + 0 x 1! + 0 x 0!

注意：由于阶乘表达式只是求和，因此我们不需要重新计算完整表达式，只需应用一些 delta ：

  1 x 3! + 2 x 2! + 0 x 1! + 0 x 0!

= 2 x 3! + 1 x 2! + 0 x 1! + 0 x 0! - ( 1 x 3!) + ( 1 x 2!)

= 14 - ( 1 x 3!) + ( 1 x 2!)

阶乘项的提取在前两行代码中完成，并且 delta 在最后一行应用。

注意：我们需要小心，因为我们交换了元素，Lehmer 代码内的索引可能已更改，并且可以选择向阶乘内的项添加 1 或删除 1：

=> 14 - ( 1 x 3!) + ( 0 x 2!)

= 14 - 6 = 8

最后一部分是在 C# 代码中的两个“if”条件中完成的