寻找优于 O(n^2) 的算法来表示排列的“阶乘基数”

Question

我正在寻找一种有效的算法来计算给定n排列的阶乘基表示(又名"康托尔展开"(。

我所说的"高效"是指运行时间优于O(n2)。

---

(顺便说一句，我意识到有多种自然方法可以将排列映射到阶乘基表示，仅在采用的约定上有所不同，并且我正在寻找的算法在某种程度上取决于选择的特定约定。 目前我对这个问题没有强烈的偏好，尽管这主要基于未经证实的假设，即为一组约定编写的任何算法都很容易转换为支持一组不同约定的算法，而不会对运行时间产生任何不利影响。

FWIW，一种O(n2)时间算法的示例，用于计算列表排列的阶乘基表示(0, 1, ..., n-1)该算法将计算此类表示的第i位数字，d_i，例如i-th元素与排列中的某些后续元素之间的反转次数(在给定的排列中(。

或者，在伪代码中，(假设从 0 开始的数组(：

function FACTORIAL_REPRESENTATION(p):
    n <- length(p)
    d <- zeros(n - 1)
    for i <- 0 to n - 3:
        for j <- i + 1 to n - 2:
            if p[i] > p[j]:
                d[i] <- d[i] + 1
    return d

例如，给定 [0， 1， 2， 3] 的排列 [2， 3， 1， 0]，

上面的函数应该返回数组 [2， 2， 1]，对应于反转

2 ： [2， 3， 1， 0]，
• [2， 3， 1， 0]
2 ： [2， 3， 1， 0]，
• [2， 3， 1， 0]
• 1 ： [2， 3， 1， 0]

由于

计数反转在我看来类似于排序，并且由于排序可以在O(nlogn)中完成，我想至少可能有一个O(nlogn)算法来做到这一点，但我无法想出它。

Answer 1

你的循环

    for j <- i + 1 to n - 2:
        if p[i] > p[j]:
            d[i] <- d[i] + 1

只是一个排名查询;你想知道i日之后p有多少元素小于p[i]。 您可以修改平衡二叉搜索树，以报告元素在对数时间中的秩以及其常规操作。 您可以初始化这样的树以包含所有p 。 然后，您将d[i]设置为rank(p[i])并删除p[i]。 (您也可以向后运行循环并进行插入而不是删除。