1

维基百科上描述的 Fisher yates 算法是

该算法产生一个无偏的排列：每个排列都是同样可能的。

我浏览了一些文章，这些文章解释了一个朴素的和 Fisher yates 算法如何产生一组有偏见和无偏见的项目组合。

链接到文章

Fisher-Yates Shuffle – 每个开发人员都应该知道的算法

随机性很难：学习 Fisher-Yates shuffle 算法和随机数生成

文章继续展示了这两种算法的几乎无偏见和非常有偏见的结果图。我试图重现概率，但我似乎无法产生差异。

这是我的代码

import java.util.*

class Problem {
    private val arr = intArrayOf(1, 2, 3)
    private val occurrences = mutableMapOf<String, Int>()
    private val rand = Random()

    fun biased() {
        for (i in 1..100000) {
            for (i in arr.indices) {
                val k = rand.nextInt(arr.size)
                val temp = arr[k]
                arr[k] = arr[i]
                arr[i] = temp
            }


            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Naive:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }

    /**
    * Fisher yates algorithm - unbiased
    */
    fun unbiased() {
        for (i in 1..100000) {
            for (i in arr.size-1 downTo 0) {
                val j = rand.nextInt(i + 1)
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }

            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Fisher Yates:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }
}

fun main() {
    Problem().biased()
    Problem().unbiased()
}

这会产生以下结果

Naive:
312: 16719
213: 16654
231: 16807
123: 16474
132: 16636
321: 16710
Fisher Yates:
123: 16695
312: 16568
213: 16923
321: 16627
132: 16766
231: 16421

在这两种情况下，我的结果并没有太大的不同。我的问题是，我的实现错了吗？还是我的理解有误？

4

1 回答 1

3

您对这两种算法的实现都有一个错误，它消除了由天真的洗牌引入的偏差。您不会从每次 shuffle 的相同排列开始，而是从最后一次 shuffle 产生的排列开始。一个简单的解决方法是将数组重置为[1, 2, 3]每次：

import java.util.*

class Problem {
    private var arr = intArrayOf(1, 2, 3)
    private val occurrences = mutableMapOf<String, Int>()
    private val rand = Random()

    fun biased() {
        for (i in 1..100000) {
            arr = intArrayOf(1, 2, 3)  // reset arr before each shuffle
            for (i in arr.indices) {
                val k = rand.nextInt(arr.size)
                val temp = arr[k]
                arr[k] = arr[i]
                arr[i] = temp
            }


            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Naive:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }

    /**
    * Fisher yates algorithm - unbiased
    */
    fun unbiased() {
        for (i in 1..100000) {
            arr = intArrayOf(1, 2, 3)  // reset arr before each shuffle
            for (i in arr.size-1 downTo 0) {
                val j = rand.nextInt(i + 1)
                val temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
            }

            val combination = arr.toList().joinToString("")

            if (occurrences.containsKey(combination)) {
                occurrences[combination] = occurrences[combination]!! + 1
            } else {
                occurrences[combination] = 1
            }
        }

        print("Fisher Yates:\n")
        occurrences.forEach { (t, u) ->
            print("$t: $u\n")
        }
    }
}

fun main() {
    Problem().biased()
    Problem().unbiased()
}

输出：

Naive:
213: 18516
132: 18736
312: 14772
321: 14587
123: 14807
231: 18582
Fisher Yates:
321: 16593
213: 16552
231: 16674
132: 16486
123: 16802
312: 16893

不是 Kotlin 程序员，所以可能有一种更优雅的方式来做到这一点，但我想它已经足够好了。

于 2021-05-15T11:28:27.187 回答