1

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

“高效”是指比运行时间更好的。O(n2)

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

FWIW，计算列表排列的阶乘基表示的 -time 算法的一个示例是计算-之间的倒数（在给定排列中）这样表示的第-位th 元素和排列中的一些后续元素。 O(n2)(0, 1, ..., n-1)id_ii

或者，在伪代码中，（假设基于 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)算法可以做到这一点，但我还没有想出它。

4

1 回答 1

1

你的循环

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

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

于 2013-08-04T14:20:44.317 回答