错排

用于生成随机错排并映射值、计算逆映射和获取底层映射的库

问题

这个库是为特定的项目而创建的，但任何问题、改进或建议都将受到欢迎！

什么是错排？

错排是没有固定点的排列

什么是排列？

我们可以将排列视为一组值的重新排列。所以如果我们有一个列表 [0, 1, 2]，那么这个列表的一个排列可以是 [0, 2, 1]。

要从前者得到后者，我们注意到 0 映射到 0，1 映射到 2，2 映射到 1。我们可以写成

(0 1 2)
(0 2 1)

其中上面的数字映射到下面的数字。我们也可以用循环形式来写，其中每个数字映射到循环中的下一个数字，循环之间用括号隔开

(0)(1 2)

请注意，循环的顺序是该循环中元素的数量（因此 (0) 的顺序是 1，(1 2) 的顺序是 2）

如果一个元素映射到自身，它就是一个固定点。它也位于一个顺序为 1 的循环中（如上面的例子中的 0）

如何生成一个随机错排？

错排算法最重要的方面是注意到错排是一个排列群，其中所有循环的顺序都大于 2。这意味着我们可以利用这个事实将一组数字划分成顺序大于 2 的循环。

因此，我们定义了一个算法来随机生成错排

1. 生成一个从 0 到 size-1 的数字列表
2. 随机打乱这个列表
3. 生成一个随机数，并使用这个数作为循环的大小。
4. 重复步骤 3，直到没有元素可以划分，或者剩下 2 个元素

每次划分列表时，都至关重要，我们不能允许任何顺序为 1 的循环，从而防止固定点。因此，如果我们有 n 个元素可以划分，那么下一个划分的范围可以是 [2, n-1) ∩ { n }。

我们不能允许将 n-1 分区，因为这会留下一个成为固定点的元素。