如何找到一个K-排列从n个元素的索引？ [英] How to find the index of a k-permutation from n elements?

问题描述

我知道，对于一个 K大小 -permutation P K ，从建 N 元素有：

I know that, for a k-permutation p of size k, built from n elements, there are:

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

可能 K -permutations。例如：

possible k-permutations. For example:

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的指数 -permutation P ？考虑排列 要字典顺序产生。

So, how do I find the index of the k-permutation p? Consider the permutations to be generated lexicographically.

修改： 我可以通过寻找开始在块 P ，通过 P 的第一个元素地址块。例如， P = [3，2，4] ，该指数 P 至少应为12（从0计数到 P（N，K） - 1 ）

Edit: I could start by finding in which "block" p is, addressing the block by the first element of p. For example, for p = [3, 2, 4], the index for p should be at least 12 (counting from 0 to P(n, k) - 1).

不过，要找到块里面的第二个元素，我必须看看有哪些其余的项目被发现，并在其中的位置，他们将。我的意思是，我会最终解决列表 [1,4] ，和4将在位置2，所以只需使用元素作为重点，需要一些额外的操作

But then, to find the second element inside that "block", I'd have to see what are the remaining items to be found, and in which position they will be. I mean, I'd be eventually addressing the list [1, 4], and 4 would be at position 2, so simply using the element as key would require some extra manipulation.

我可以使用哈希来查找元素和更新自己的立场，但它会给我一个为O（n ^ 2）时间复杂度。是否有可能做的更好吗？

I could use a hash to look up the elements and update their positions, but it'd give me a O(n^2) time complexity. Is it possible to do any better?

推荐答案

排列在给定位置的给定数字的数量由一个公式给出 （正数位）！ /（N-K）！其中，数位开始在左边1。

The number of permutations for a given digit in a given position is given by a formula (n-digit position)! / (n-k)! where digit position starts on the left with 1.

要得到的preceding排列对于给定的置换（即，其索引），乘式为每一个数字由尚未使用preceding的位数，并把它们加起来。数

To get the number of preceding permutations for a given permutation (that is, its index), multiply the formula for each digit by the number of preceding digits not already used, and add them up.

实施例1中，k = 2，n = 4时，p值= [3,4]

Example 1, k = 2, n = 4, p = [3,4]

第一个数字，3： （4-1）！ /（4-2）！ *（未使用preceding位数，2）= 6 有六个排列preceding第一，拥有3个在位置1。

First digit, 3: (4-1)! / (4-2)! * (number of unused preceding digits, 2) = 6 There are six permutations preceding the first that has 3 in position 1.

二位，4： （4-2）！ /（4-2）！ *（未使用preceding位数，2）= 2 有两种排列preceding第一，在位置2有4个。

Second digit, 4: (4-2)! / (4-2)! * (number of unused preceding digits, 2) = 2 There are two permutations preceding the first that has 4 in position 2.

零基指数：6 + 2 = 8

Zero based index: 6 + 2 = 8.

实施例2中，k = 3，N = 4，p值= [3,2,4]

Example 2, k = 3, n = 4, p = [3,2,4]

第一个数字，3： （4-1）！ /（4-3）！ *（未使用preceding位数，2）= 12 有12个排列preceding第一，拥有3个在位置1。

First digit, 3: (4-1)! / (4-3)! * (number of unused preceding digits, 2) = 12 There are 12 permutations preceding the first that has 3 in position 1.

二位，2： （4-2）！ /（4-3）！ *（未使用preceding位数，1）= 2 有两种排列preceding第一个有2个位置2。

Second digit, 2: (4-2)! / (4-3)! * (number of unused preceding digits, 1) = 2 There are two permutations preceding the first that has 2 in position 2.

第三位，4： （4-3）！ /（4-3）！ *（未使用preceding位数，1）= 1 有一个置换preceding第一，在第3位有4个。

Third digit, 4: (4-3)! / (4-3)! * (number of unused preceding digits, 1) = 1 There is one permutation preceding the first that has 4 in position 3.

从零开始的索引：12 + 2 + 1 = 15

Zero based index: 12 + 2 + 1 = 15.

这篇关于如何找到一个K-排列从n个元素的索引？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！