使用 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 的文章 但我不确定这对这里有帮助。
最佳答案
(回答我自己的问题)
我终于知道了。我花了一段时间,但这是最终公式:
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”条件中完成的
关于c# - 从映射到排列的数字,如何生成不同于先前 perm 的其他排列。通过交换元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20387792/