algorithm - 为 “factorial base” 排列表示寻找优于 O(n^2) 的算法

Question

我正在寻找一种有效的算法来计算 factorial-base representation (又名“Cantor 展开”)给定的 n -排列。

“高效”是指比 O(n<sup>2</sup>) 更好的一个运行时间。

---

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

FWIW，一个 O(n<sup>2</sup>) 的例子计算列表排列的阶乘基本表示的时间算法 (0, 1, ..., n-1)将是计算 i 的一个-th 数字，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, < em>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

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