我怎样才能确保当我洗牌时我仍然能得到均匀的排列？

I'm interested making an implementation of the 14-15 puzzle:

我正在创建一个数组，其值按升序排列为 0 - 15：

S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

现在，我想做的是将它们洗牌以创建拼图的新实例。然而，我知道，如果我创建一个具有“奇数排列”的棋盘，那么它是无法解决的。

维基百科说我需要创建具有均匀排列的谜题。我相信这意味着我只需确保进行偶数次交换？

我将如何修改 Fisher-Yates 以便确保最终得到均匀的排列？如果我对数组中的每个元素进行交换，则将进行 16 次交换，我相信这将是一个偶数排列。但是，我需要担心与自身交换吗？还有其他方法可以确保我有一个有效的谜题吗？

您应该能够使用 Fischer-Yates。

• 使用 Fischer-Yates 生成随机排列。
• 检查是否均匀。
• 如果不是偶数，则交换排列的前两个元素。

考虑偶数排列 P = x1 x2 .... xn。

Fisher yates 以 1/n! 的概率生成 P。

它以 1/n! 的概率生成 x2 x1 ... xn。

因此上述过程生成排列P的概率是2/n！ = 1/(n!/2)

n!/2 是偶数排列的数量。

因此，上述过程以相同的概率生成偶数排列。

检查排列是否为偶数：计算排列的奇偶性倒转在排列中。