Алгоритм фишера-йейтса не дает объективных результатов

Question

Алгоритм Фишера Йейтса, описанный в Википедии,

Алгоритм производит беспристрастную перестановку: каждая перестановка одинаково вероятна.

Я просмотрел несколько статей, в которых объясняется, как алгоритм наивного и рыболовного Ятса может создавать предвзятые и непредвзятые комбинации элементов в наборе.

Ссылка на статьи

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

Мои результаты не сильно отличаются в обоих случаях. У меня вопрос, неправильная ли моя реализация? Или мое понимание неверно?

Answer 1

В вашей реализации обоих алгоритмов есть ошибка, которая сглаживает предвзятость, вызванную наивной перетасовкой. Вы не начинаете заново с одной и той же перестановки для каждого тасования, а с той, которая была произведена в результате последнего тасования. Простое исправление - сбросить массив до [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, так что, вероятно, есть более элегантный способ сделать это, но я думаю, он достаточно хорош.