c# - 从映射到排列的数字，如何生成不同于先前 perm 的其他排列。通过交换元素？

Question

使用 Lehmer code , 任何 permutation可以使用 factorial number system 对包含 N 个元素的序列进行编码并将其映射为十进制数。 .

示例:

ABCD 排列的 Lehmer 代码:

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

这些反转向量可以使用阶乘转换为小数:

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 algorithm 的文章但我不确定这对这里有帮助。

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!

注意:由于阶乘表达式只是一个总和，我们不需要重新计算整个表达式，只需应用一些增量即可:

  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!)

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

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

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

= 14 - 6 = 8

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