1

我正在研究 15 片滑动拼图的实现，我被困在我必须确保我只洗牌成“可解决的排列”的点上——在我的例子中，右下角的空瓷砖：甚至排列。

我已经阅读了许多类似的主题，例如如何确保当我洗牌时我仍然得到一个偶数排列？并了解我需要“计算排列中反转次数的奇偶性”。

我正在用 Javascript 编写，并使用 Fischer-Yates-algorithm 随机化我的数字：

var allNrs = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14];
for (var i = allNrs.length - 1; i > 0; i--) {
   var j = Math.floor(Math.random() * (i + 1));
   var temp1 = allNrs[i];
   var temp2 = allNrs[j];
   allNrs[i] = temp2;
   allNrs[j] = temp1;
}

我如何实际计算我在这么多帖子中读到的排列或奇偶校验值？

4

2 回答 2

2

只需计算您进行的交换次数即可。如果交换次数是偶数，则排列具有偶校验。

例如，这些是 3 个数字的偶数排列。请注意，您需要 0 或 2 次交换才能从 [1,2,3] 获取它们：

1,2,3
2,3,1
3,1,2
于 2013-05-25T00:30:35.357 回答
0

您所做的两个数字的每次交换都会翻转奇偶校验。如果你有一个偶数，你很好。如果你有一个奇数，你不是。

这本质上就是奇偶性的含义，它是群论的一个（简单）定理，即任何两种达到相同洗牌的方法都具有相同的奇偶性。

于 2013-05-25T00:35:40.740 回答