java - 如何计算排列中的交换次数？

Question

我下面有这段代码，我想知道如何计算交换次数。我使用计数变量来计算它，但我得到的数字与计算机不同。我认为交换次数为 2 * (n - 1)(n - 2)...(n - n + 1)。对于 n == 4，计算机得到 128，而我得到 48。我做错了什么？

public void permute(int n) {
        if (n == 1) {
            printOutPut();
        }
        for (int i = 1; i <= n; i++){
          swap(i, n);
          permute1(n-1);
          swap(i, n);
        }
    }

Answer 1

代码定义了递归:

num_swaps(0) = 0
num_swaps(i) = i * (num_swaps(i - 1) + 2)

或者使用更多类似数学的符号:

s_{n+1} = (n + 1) (s_n + 2)
s_0 = 0
s_1 = 2
s_2 = 8
s_3 = 30
s_4 = 128

您可能可以使用数学技术来解决一般 n 的递归问题，但这验证了计算机是否正确

编辑:我试图找到通用n的解决方案，最终得到了wolfram alpha，并且提出的解决方案具有不完整的gamma函数和东西。所以，不要指望计算会很容易!