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

Question

我知道，对于大小为 k 的 k 排列 p，由 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 的索引？考虑排列 按字典顺序生成。

编辑: 我可以从查找 p 所在的“ block ”开始，通过 p 的第一个元素寻址该 block 。例如，对于 p = [3, 2, 4]，p 的索引应至少为 12(从 0 到 P(n, k ) - 1).

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

我可以使用散列来查找元素并更新它们的位置，但它会给我 O(n^2) 时间复杂度。有没有可能做得更好？

Answer 1

给定位置给定数字的排列数由公式给出 (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 在位置 1 有 3 个的第一个排列之前有 12 个排列。

第二个数字，2: (4-2)!/(4-3)! *(未使用的前位数，1)= 2 在位置 2 为 2 的第一个排列之前有两个排列。

第三位，4: (4-3)!/(4-3)! *(未使用的前位数，1)= 1 第一个排列之前有一个排列，位置 3 为 4。

从零开始的指数:12 + 2 + 1 = 15。