最近，我正在思考怎样实现一个时间复杂度小于等于 $O(n)$ 的，可以随机打乱长度为 $n$ 的数组 $a_0,a_1,a_2,\cdots,a_{n-1}$ 的在线算法。考虑到时间复杂度不能太高，又要在线打乱，我设计了如下代码，使其在输入 $a_i(i>0)$ 时，可以随机选择一个 $[0,i]$ 内的整数 $j$，并交换 $a_i,a_j$（这大致也是 random_shuffle 的实现思路）：

#import<bits/stdc++.h>
int a[10000],n,t,j;
main(){
	srand(1ll*time(0)*time(0)%0x7fffffff);
	while(~scanf("%d%d",&n,a)){
		for(int i=1;i^n;++i)scanf("%d",a+i),t=a[i],a[i]=a[j=rand()%(i+1)],a[j]=t;
        for(int i=0;i^n;++i)printf("%d ",a[i]);
	}
}

在运行程序时，我发现，在 $n\leqslant3$ 且 $a_i=i$ 时（即在 $a_i$ 互不相等的情况下），程序可以几乎等概率地输出 $0\sim n-1$ 的任意一个排列，而打乱较大数据的效果也很好。我想，对于任意的 $n$，这个算法是不是永远都如此呢？为此，我写了如下代码进行检验：

#import<bits/stdc++.h>
int a[5],n,t;
void _(int d){//dfs
	if(d^n)for(int i=0;i<=d;++i)t=a[d],a[d]=a[i],a[i]=t,_(d+1),t=a[d],a[d]=a[i],a[i]=t;//模拟每一种交换
	else{
		for(int i=0;i^n;++i)printf("%d ",a[i]);
		putchar(10);
	}
}
main(){
	while(~scanf("%d",&n)){
		for(int i=0;i^n;++i)scanf("%d",a+i);_(1);
	}
}

我原以为，上面的结论（程序可以等概率输出原数组的排列）只是巧合。谁知，上面程序的输出则更让我惊讶了：在 $n\leqslant5$ 时，程序竟将 $a$ 的全部排列输了出来，并且似乎在某种意义上，这些排列本身的输出就井然有序。

看到这样的结果，我更加疑惑了。在 $a_i$ 互不相等的情况下，$a$ 的不同排列个数便有且只有 $\text A_n^n=n!$ 种，而在实现我设计的随机打乱数组算法中，$n-1$ 次交换的情况也恰有 $\prod\limits_{i=2}^n=n!$ 种不同的可能。如果上述结论确实成立，那岂不是对于任意一个 $a$ 的排列，都恰好对应了一种交换方式，这是多么不容易的事情！假设 rand()%(i+1) 取到各个 $[0,i]$ 范围内的数的概率相等，这两段代码的“神奇之处”真的存在，真的可以等概率进行数组打乱、在 $a_i$ 互不相等的情况下输出 $a$ 的全排列吗？