Shuffle isn't correct

[niyaznigmatullin]

fun <T:Comparable<T>>shuffle(items:MutableList<T>):List<T>{
    val rg : Random = Random()
    for (i in 0..items.size - 1) {
        val randomPosition = rg.nextInt(items.size)
        val tmp : T = items[i]
        items[i] = items[randomPosition]
        items[randomPosition] = tmp
    }
    return items
}

This algorithm doesn't shuffle it correctly, not every permutation is equiprobable. You have to do:

val randomPosition = rg.nextInt(i + 1)

to fix it.

More information:
https://blog.codinghorror.com/the-danger-of-naivete/

[peheje]

Maybe this is correct

import java.util.*

val random = SplittableRandom()

fun wrongShuffle(x: MutableList<Int>): List<Int> {
    for (i in 0 until x.size) {
        val n = random.nextInt(x.size)
        x[i] = x[n].also { x[n] = x[i] }
    }
    return x
}

fun maybeCorrectShuffle(x: MutableList<Int>): List<Int> {
    for (i in x.size downTo 2) {
        // downTo 2 because if down to 1: 1-1 = 0 so we would swap idx 0 with idx nextInt(0) which would fail.
        val n = random.nextInt(i)
        x[i-1] = x[n].also { x[n] = x[i-1] }
    }
    return x
}

fun main(args: Array<String>) {
    val iterations = 1_000_000
    val cards = listOf(1, 2, 3)
    val permutations = mutableListOf<List<Int>>()
    val counts = mutableMapOf<List<Int>, Int>()

    for (i in 0 until iterations) {
        val shuffledCards = maybeCorrectShuffle(cards.toMutableList())
        // Collections.shuffle(shuffledCards)
        permutations.add(shuffledCards)
    }

    println(permutations)

    for (perm in permutations) {
        if (counts.containsKey(perm)) counts[perm] = counts[perm]!! + 1 else counts[perm] = 1
    }

    println(counts)
}

[niyaznigmatullin]

Actually, you would swap 0 with nextInt(1) which is also 0, so there is no need, for sure.

[peheje]

Ah true. But yea you can skip going down to index 0 as the swap would always be with itself. Thanks for the interesting read at codinghorr niyaznigmatullin.