我怎样才能确保在洗牌时仍能得到均匀的排列? [英] How can I ensure that when I shuffle my puzzle I still end up with an even permutation?

问题描述

我有兴趣实施 14-15难题:

我正在创建一个值从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.

Fischer yates生成概率为1/n！的P.

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

因此，上述过程生成置换P的概率为2/n！ = 1/(n！/2)

n！/2是偶数排列的数量.

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

要检查排列是否是偶数:在中计算 inversions 的数量的奇偶校验排列.

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

I'm creating an array with the values 0 - 15 in increasing order:

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

Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I create a board with an "odd permutation" than it is unsolvable.

Wikipedia says I need to create the puzzle with an even permutation. I believe this means that I simply have to do ensure I do an even number of swaps?

How would I modify Fisher-Yates so I ensure I end up with an even permutation at the end? If I do a swap for every element in the array that would be 16 swaps which I believe would be an even permutation. However, do I need to be concerned about swapping with itself? Is there any other way to ensure I have a valid puzzle?

解决方案

You should be able to use Fischer-Yates.

• Generate a random permutation using Fischer-Yates.
• Check if it is even.
• If it is not even, swap the first two elements of the permutation.

Consider an even permutation P = x1 x2 .... xn.

Fischer yates generates P with probabilty 1/n!.

It generates x2 x1 ... xn with probability 1/n!.

Thus the probability that the above process generates the permutation P is 2/n! = 1/(n!/2)

n!/2 is the number of even permutations.

Thus the above process generates even permutations with same probability.

To check if a permutation is even: count the parity of the number of inversions in the permutation.

这篇关于我怎样才能确保在洗牌时仍能得到均匀的排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！