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

Question

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

3

我知道，对于一个大小为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

那么我如何找到p的k排列的索引呢？考虑按字典顺序生成排列。编辑：我可以开始找出p所在的“块”，并通过p的第一个元素寻址该块。例如，对于p = [3, 2, 4]，p的索引应至少为12（从0到P(n，k)-1进行计算）。

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

我可以使用哈希来查找元素并更新其位置，但这将给我带来O（n ^ 2）的时间复杂度。有没有可能做得更好？

- Rubens

1

可能的起点：http://en.wikipedia.org/wiki/Lehmer_code#Encoding_and_decoding - Kaz

@Kaz 非常感谢您提供的参考。我会去查看它，也会尝试使用TXR。我一直在考虑介绍自己学习Lisp，现在我将尝试学习Lisp和TXR。谢谢。 - Rubens

4个回答

2

TXR language:

$ txr -p "(pos '(1 4 3) (perm '(1 2 3 4) 3))"
5

这是一种暴力破解方法，但是当然，pos并不知道排列的结构。

- Kaz

谢谢你的回答。请检查我的编辑。我忘记添加我已经想到的内容，以及我确切地寻找的答案。 - Rubens

是的，你正在寻找一个快速算法，而不仅仅是任何旧代码来输出答案。 - Kaz

1

使用二叉搜索树（BST）。在开始之前将所有数字存储在其中，并在使用一个数字后将其删除。为了找到第x个元素，维护每个顶点的.subtreeSize，只需沿着树下降即可找到所需的数字。伪代码：

    def findXth(x):
        curVertex = BST.root
        while:
            curPosition = curVertex.leftChild.subtreeSize
            if curPosition == x: return curVertex.value
            elif curPosition > x: curVertex = curVertex.leftChild
            elif curPosition < x: curVertex = curVertex.rightChild

不要忘记检查顶点是否存在并删除找到的顶点。

总体复杂度将是O(n log n)。

- Paul

0

您可以参考下面的函数

 /**
 *  list all k or <=k size permutation of a given list with n unique elements.
 *  n can be bigger than 64. this function will take O(K^N) time, Bad.
 *
 * @param uniqueList
 * @param permutationSize
 * @param permutation
 * @param only            Only show the permutation of permutationSize,
 *                        else show all permutation of less than or equal to permutationSize.
 */
public static void my_permutationOf(List<Integer> uniqueList, int permutationSize, List<Integer> permutation, boolean only) {
    if (permutation == null) {
        assert 0 < permutationSize && permutationSize <= uniqueList.size();
        permutation = new ArrayList<>(permutationSize);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
    }
    for (int i : uniqueList) {
        if (permutation.contains(i)) {
            continue;
        }
        permutation.add(i);
        if (!only) {
            System.out.println(Arrays.toString(permutation.toArray()));
        } else if (permutation.size() == permutationSize) {
            System.out.println(Arrays.toString(permutation.toArray()));
        }
        if (permutation.size() < permutationSize) {
            my_permutationOf(uniqueList, permutationSize, permutation, only);
        }
        permutation.remove(permutation.size() - 1);
    }
}

例如，您可以将该元素视为索引。

public static void main(String[] args) throws Exception {
    my_permutationOf(new ArrayList<Integer>() {
        {
            add(0);
            add(1);
            add(2);
            add(3);

        }
    }, 3, null, true);
}

结果是

[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
[0, 3, 1]
[0, 3, 2]
[1, 0, 2]
[1, 0, 3]
[1, 2, 0]
[1, 2, 3]
[1, 3, 0]
[1, 3, 2]
[2, 0, 1]
[2, 0, 3]
[2, 1, 0]
[2, 1, 3]
[2, 3, 0]
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]

- Bruce Zu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

给定数字在给定位置的排列数由公式 (n-digit position)! / (n-k)! 给出，其中数字位置从左侧第一个开始为1。

要获得给定排列的前置排列数（即其索引），请将每个数字的公式乘以未使用的先前数字数量，并将它们相加。

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

第一个数字 3： (4-1)! / (4-2)! *（未使用的前导数字数量2）= 6 有六个排列在第一个位置为3的排列之前。

第二个数字 4： (4-2)! / (4-2)! *（未使用的前导数字数量2）= 2 有两个排列在第一个位置为4的排列之前。

零基索引：6 + 2 = 8.

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

第一个数字 3： (4-1)! / (4-3)! *（未使用的前导数字数量2）= 12 有12个排列在第一个位置为3的排列之前。

第二个数字 2： (4-2)! / (4-3)! *（未使用的前导数字数量1）= 2 有两个排列在第二个位置为2的排列之前。

第三个数字 4： (4-3)! / (4-3)! *（未使用的前导数字数量1）= 1 有一个排列在第三个位置为4的排列之前。

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