对于一个数组，所有的排列一共存在多少种呢？根据排列组合

对于一个数组，所有的排列一共存在多少种呢？根据排列组合，对 nnn 个不同元素进行排列，从第 111 位开始枚举，选择 1 n1~n1 n 中的某一个，然后进行第 222 位的枚举，选择剩下的 n−1n-1n−1 个中的某一个，依次直到选取最后一个元素，很容易知道这样的排列总数为 n!n!n!。

洗牌算法的核心在于能等概率的产生所有可能的排列情况。

看到这个题目，首先就想到的是新建一个数组 src\textit{src}src，用于存储原始数组，然后调用reset()时直接返回这个数组 src\textit{src}src。

然后，如何随机打乱一个数组呢？

上述代码比较晦涩难懂，优化为下面的代码：

空间复杂度：O(n)，记录初始状态和临时的乱序数组均需要存储 nnn 个元素。

这里的nnn就是你先挑选出第一个元素的种类数，而 (n−1)!(n-1)!(n−1)! 就是对其他元素的排列。

我们需要挑选一种洗牌方案：

先等概率的从 nnn 个元素中挑选一个作为第一个元素；

再对剩下的 n−1n-1n−1 个元素做类似的选择；

依次类推，直到没有元素可选为此。

可以理解为把 n!n!n! 分成 nnn 段，先选择其中一段，里面有 (n−1)!(n-1)!(n−1)! 个元素，我们把这 (n−1)!(n-1)!(n−1)! 个情况再分成 n−1n-1n−1 段，从中随机选一个，这样每个数都有相等的概率被放到任意一个位置中，即每个位置中出现任意一个数的概率都是相同的。