有效地计数排列(n个元素没有不动点的排列次数)

Question

我有一个数字n，我想找出有多少种方法可以创建一个从1到n有n个不同元素的数组，使得对于没有索引I的数组a [I] = I

例如N = 4，我们有9个排列
[2 1 4 3]，[2 3 4 1 1]，[2 4 1 3]，[3 1 4 2]，[3 4 2 1]，[4 1 2 3]，[4 3 1 2]，[4 3 2]，[4 3 2]，[4 3 2]，[4 3 2]，[4 3 2]，[4 3 2]，[4 3 2]，[4 3 2]。

我知道蛮力方法的时间复杂度为O(n!)。还有其他优化的方法吗?复杂度为O(n)或O(nlogn)的东西

Answer 1

{1,2，…，n}中没有元素出现在其位置的称为无序。您正在寻找n个元素集合的排列数，其中有一个公式(可以使用包含-排除原理获得)。公式是$n!sum_{i=0}^n (-1)^i/i!$。参见维基百科关于错乱的文章，该文章推导了这个公式。

在极限情况下，该值趋近于n!/e，大约是0.37 n!，即37%的n!排列就是无序。

Answer 2

计数排列问题可以用动态规划在线性时间O(n)内求解，这得益于欧拉证明了递归关系:

!n = (n-1) * (!(n-1) + !(n-2))

这允许从下至上而不是递归地解决问题，跟踪前面的两个项!(n-1)和!(n-2)(例如。在javascript中):

function a(n) {
if (n < 3) {
return n < 0 ? undefined : Math.abs(n-1);
}
// For n = 3, we got :
let x = 1; // !(n-1)
let y = 0; // !(n-2)
for (let k=3; k<=n; k++) {
const fk = (k - 1) * (x + y);
[x, y] = [fk, x];
}
return x;
}    

欧拉还证明了另一个递归关系:

!n = n * !(n-1) + (-1)^n

使用相同的技术，只有一个前项(变量)需要跟踪。这转换为:

function a(n) {
if (n < 3) {
return n < 0 ? undefined : Math.abs(n-1);
}
let x = 1; // !(n-1) for n = 3
for (let k=3; k<=n; k++) {
x = k*x + (-1)**k;
}
return x;
}