查找后序 BST 排列的数量

Question

我正在处理一个问题，上面写着： 找到从 1 到 n 个 BST 的排列（后序遍历）。 例如，对于 n = 3：我们有 6！ - 1 = 5 种排列，因为 (3 1 2) 不是 BST 后序。

我为此编写了一个算法，例如 n = 4：

我们总共有 3!+2!+2!+3! = 16

我已经使用此算法编写了这段代码来计算从 1 到 n 的排列数：

int calcPerm(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        sum += (fact(n-1-i) * fact(i));
    }
    return sum;
}

我知道一些 n, 1 <= n <= 20 it gives me a wrong answer and I don't know why its not working. Any help would be appreciated.

Answer 1

阶乘增长很快，超出了 32 位整数的范围。但退一步来说，这个公式（算法）是不正确的。你写：

为此编写一个算法，例如 n = 4： [...] 总共我们有 3!+2!+2!+3! = 16

但是 16 并不是 𝑛 = 4 的正确结果。它应该是 14。

这是所有可能的后序的表格，以及它们是否可以是 BST：

邮购	有效的 BST？
1 2 3 4	是的
1 2 4 3	是的
1 3 2 4	是的
1 3 4 2	不
1 4 2 3	不
1 4 3 2	不
2 1 3 4	是的
2 1 4 3	是的
2 3 1 4	是的
2 3 4 1	是的
2 4 1 3	不
2 4 3 1	是的
3 1 2 4	不
3 1 4 2	是的
3 2 1 4	是的
3 2 4 1	是的
3 4 1 2	不
3 4 2 1	是的
4 1 2 3	不
4 1 3 2	是的
4 2 1 3	不
4 2 3 1	不
4 3 1 2	不
4 3 2 1	是的

因此，尽管你的算法给出了正确的结果 𝑛 < 4, it starts overshooting the expected outcome from 4 onwards.

加泰罗尼亚数字

可以描述 BST 的后序数实际上对应于具有 𝑛 节点的二叉树可以拥有的形状的数量。一旦树的shape被建立，就只有一种方法来用给定的数字来标记节点，这样它就是一个二叉搜索树（BST）。因此，这也唯一对应于邮购订单。

二叉树的形状数由加泰罗尼亚数字给出。

我们可以使用增量公式来计算其中的前 21 个，对于 𝑛 = 20，结果是 6,564,120,420。

int

没有足够的范围来实现此目的，因此您应该使用

long

代替。

代码：

#include <iostream>
#include <vector>

std::vector<long> getCatalans(const int n) {
    std::vector<long> results = {1};
    long c = 1;
    for (int i = 1; i <= n; ++i) {
        c = 2*(2*i - 1) * c / (i + 1);
        results.push_back(c);
    }
    return results;
}

int main() {
    std::vector<long> catalans = getCatalans(20);
    for (int n = 1; n <= 20; n++) {
        std::cout << n << ". " << catalans[n] << std::endl;
    }
}

输出：

1. 1
2. 2
3. 5
4. 14
5. 42
6. 132
7. 429
8. 1430
9. 4862
10. 16796
11. 58786
12. 208012
13. 742900
14. 2674440
15. 9694845
16. 35357670
17. 129644790
18. 477638700
19. 1767263190
20. 6564120420