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

Question

我有兴趣实现 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 次交换，我相信这将是一个偶数排列。但是，我是否需要担心与自身交换？有没有其他方法可以确保我有一个有效的谜题？

Answer 1

您应该能够使用 Fischer-Yates。

使用 Fischer-Yates 生成随机排列。

检查它是否均匀。

如果不是偶数，则交换排列的前两个元素。

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

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

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

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

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

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

要检查排列是否为偶数:计算 inversions 的数量的奇偶性在排列中。