如何从 n 个元素中找到 k 排列的索引？

我知道，对于一个k-排列p大小的k，从构建n元素，有：

P(n, k) = n! / (n - k)!

可能的k-排列。例如：

k = 2
n = 4
l = [1, 2, 3, 4]
P(n, k) = 4! / (4 - 2)! = 12

1 2 | 2 1 | 3 1 | 4 1
1 3 | 2 3 | 3 2 | 4 2
1 4 | 2 4 | 3 4 | 4 3

还有另一个例子：

k = 3
n = 4
l = [1, 2, 3, 4]
P(n, k) = 4! / (4 - 3)! = 24

1 2 3 | 2 1 3 | 3 1 2 | 4 1 2
1 2 4 | 2 1 4 | 3 1 4 | 4 1 3
1 3 2 | 2 3 1 | 3 2 1 | 4 2 1
1 3 4 | 2 3 4 | 3 2 4 | 4 2 3
1 4 2 | 2 4 1 | 3 4 1 | 4 3 1
1 4 3 | 2 4 3 | 3 4 2 | 4 3 2

那么，如何找到该索引k-排列p？考虑排列 按字典顺序生成。

Edit： 我可以首先找到哪个“块”p是，通过第一个元素来寻址块p。例如，对于p = [3, 2, 4]，索引为p应至少为 12（从 0 到P(n, k) - 1).

但是，为了找到该“块”内的第二个元素，我必须查看要找到的剩余项目是什么，以及它们将位于哪个位置。我的意思是，我最终会处理这个列表[1, 4]，4 将位于位置 2，因此简单地使用该元素作为键将需要一些额外的操作。

我可以使用哈希来查找元素并更新它们的位置，但它会给我一个O(n^2)时间复杂度。是否可以做得更好？

给定位置上给定数字的排列数由公式给出 （n 位数字）！ / (n-k)!其中数字位置从左侧开始，从 1 开始。

要获取给定排列（即其索引）的前面排列的数量，请将每个数字的公式乘以尚未使用的前面数字的数量，然后将它们相加。

示例 1，k = 2，n = 4，p = [3,4]

第一个数字，3： （4-1）！ /（4-2）！ *（未使用的前面数字的数量，2）= 6 第一个排列之前有六种排列，其中位置 1 有 3 个排列。

第二位数字 4： （4-2）！ /（4-2）！ *（未使用的前面数字的数量，2）= 2 在第一个排列之前有两个排列，其中位置 2 为 4。

零基索引：6 + 2 = 8。

示例 2，k = 3，n = 4，p = [3,2,4]

第一个数字，3： （4-1）！ /（4-3）！ *（未使用的前面数字的数量，2）= 12 第一个排列之前有 12 个排列，其中位置 1 有 3 个排列。

第二位数字 2： （4-2）！ /（4-3）！ *（未使用的前面数字的数量，1）= 2 在第一个排列之前有两个排列，其中位置 2 为 2。

第三位数字 4： （4-3）！ /（4-3）！ *（未使用的前面数字的数量，1）= 1 第一个排列之前有一个排列，其位置 3 为 4。

零基索引：12 + 2 + 1 = 15。