algorithm - 计算 n 个对象在关系 < 和 = 下的可能排序数

Question

问题来了:

给出一个以正整数 n 作为输入的算法，并计算可能排序的数量在关系 < 和 = 下的 n 个对象。例如，如果 n = 3，则 13 种可能的排序如下:

a = b = c, 
a = b < c, 
a < b = c, 
a < b < c, 
a < c < b, 
a = c < b, 
b < a = c, 
b < a < c, 
b < c < a,
b = c < a, 
c < a = b, 
c < a < b, 
c < b < a. 

你的算法应该在 n 的时间多项式中运行。

我对这个问题一无所知。你能找到解决这个动态规划问题的方法吗？

Answer 1

The code

设 f(n,k) 是具有恰好 k 个不等式关系(和 (n - 1 - k) 质量关系)的可能排序的数量。

不难看出，f(n,0) = 1, f(n,n-1) = n!对于任何 n.

现在我们要计算任意 k 的 f(n,k)。想象一下，您移开了一个数字(任意)，所以现在有 (n-1) 个数字。有两种可能:

1) 在这 (n-1) 个数字中有 (k-1) 个不等式，并且有 (k+1)(f(n-1,k-1)) 种方法可以添加第 n 个数字所以增加了新的不平等。

2) 这(n-1)个数有k个不等式，有(k+1)(f(n-1,k))种方法添加第 n 个数字，没有额外的不等式。

所以，f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k))。

最终答案 F(n) = f(n,0) + f(n,1) + ... + f(n,n-1)。