algorithm - 铃数算法

Question

我正在尝试编写一种算法来找出可以对 n 个数字进行排序的方式的数量。例如，两个数字 a 和 b 可以用 3 种方式排序..

同理，3个数可以有13种排列方式。

我发现我可以使用动态规划来解决这个问题。这就是我想拥有代表不同顺序的层。前任。 a > b 有两层，a = b 有一层，依此类推。这样我就可以像在动态编程中那样将其用于以后的目的。但是我不能为它写一个递归关系。有人可以建议我怎么写吗？

Answer 1

假设 f(n,k) = 有 k 个不等式(因此有 n-k-1 个等式)的可能方式数，所以:假设你有 n-1 个数，现在你想添加另一个数并计算 f(n,k)，那么我们有两种可能:

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))

而你想要的是它们的总和(从零到 n-1)，波纹管代码是用 c# 编写的(只是针对简单的情况进行了测试)，事实上我们只是计算可能的方式的数量，而不是生成所有的方式..

class EqualInequalPermutation
{
    public int OrderingsNumber(int n)
    {
        int[][] f = new int[n+1][];
        for (int i = 0; i < n+1; i++)
        {
            f[i] = new int[n];
            for (int j = 0; j < n; j++)
                f[i][j] = 0;
        }
        f[1][0] = 1;
        int factorial = 1;
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = 1;
            factorial *= i;
            f[i][i - 1] = factorial;
            for (int k = 1; k < n; k++)
            {
                f[i][k] = (k + 1) * (f[i - 1][k - 1] + f[i - 1][k]);
            }
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            answer += f[n][i];
        }
        return answer;
    }
}