[Kotlin] Random Permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.
This class provides handy utilities for looping through collections in random orders. This has quite a few uses in RSPS with pid shuffling, finding a random player inside of a region, spawning boss npcs in random orders, etc. This was designed to be extremely performant and wont add any allocations/latency to your application.
Code:
package io.insignia.utility
import io.insignia.api.utils.Random
import kotlin.math.ceil
import kotlin.math.ln
import kotlin.math.pow
/**
* Allows collections to be iterated through in a random order without creating any allocations.
*
* @author Gluon <[email protected]>
*/
object RandomPermutation {
// https://en.wikipedia.org/wiki/Linear_congruential_generator -> Numerical Recipes
const val c = 1_0_1_3_9_0_4_2_2_3 // NEVER CHANGE THESE
const val a = 1_6_6_4_5_2_5 // NEVER CHANGE THESE
inline fun <T> Array<T>.iterateShuffledIndexed(block: (Int, T) -> Unit) {
if (size == 0) return
doLoop(size) {
block(it, this[it])
}
}
inline fun <T> Array<T>.iterateShuffled(block: (T) -> Unit) {
if (size == 0) return
doLoop(size) {
block(this[it])
}
}
inline fun <T> List<T>.iterateShuffled(block: (T) -> Unit) {
if (size == 0) return
doLoop(size) {
block(this[it])
}
}
inline fun doLoop(size: Int, block: (Int) -> Unit) {
val m = 2.0.pow(ceil(ln(size.toDouble()) / ln(2.0))).toLong()
val seed = Random.get(size)
var next = seed.toLong()
do {
next = (a * next + c) % m
while (next >= size) {
next = (a * next + c) % m
}
block(next.toInt())
} while (next != seed.toLong())
}
}