我怎样才能确保在洗牌时仍能得到均匀的排列?

我正在创建一个值从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. 这篇关于我怎样才能确保在洗牌时仍能得到均匀的排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！