Thread: [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())
	}
	
}

Spoiler for Unit tests (if you use unit testing in your server):

Code:

package io.insignia.utility

import io.insignia.utility.RandomPermutation.iterateShuffled
import io.insignia.utility.RandomPermutation.iterateShuffledIndexed
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class RandomPermutationTest {
	
 @[Only registered and activated users can see links. ]
	fun testConstants() {
		assertEquals(1_0_1_3_9_0_4_2_2_3, RandomPermutation.c)
		assertEquals(1_6_6_4_5_2_5, RandomPermutation.a)
	}
	
 @[Only registered and activated users can see links. ]
	fun testIndexedIterator() {
		val array = fillArray(1000)
		val set = hashSetOf(*array)
		
		array.iterateShuffledIndexed { index: Int, _: Int ->
			set.remove(index)
		}
		
		assertEquals(0, set.size, "Size should be 0 instead it's ${set.size}")
	}
	
 @[Only registered and activated users can see links. ]
	fun test1000() = testArray(fillArray(1000))
	
 @[Only registered and activated users can see links. ]
	fun test100() = testArray(fillArray(100))
	
 @[Only registered and activated users can see links. ]
	fun test10() = testArray(fillArray(10))
	
 @[Only registered and activated users can see links. ]
	fun test5() = testArray(fillArray(5))
	
 @[Only registered and activated users can see links. ]
	fun test2() = testArray(fillArray(2))
	
 @[Only registered and activated users can see links. ]
	fun test1() = testArray(fillArray(1))
	
	private fun fillArray(size: Int) = Array(size) {
		it
	}
	
	private fun testArray(array: Array<Int>) {
		val set = hashSetOf(*array)
		
		array.iterateShuffled {
			set.remove(it)
		}
		
		assertEquals(0, set.size, "Size should be 0 instead it's ${set.size}")
	}
	
}

Spoiler for My random class (you can use any Random class you want):

Code:

package io.insignia.api.utils

import java.security.SecureRandom
import java.util.concurrent.ThreadLocalRandom
import kotlin.math.abs

object Random {
	
	private var x = SecureRandom().nextLong()
	
	@JvmStatic
	fun get() = ThreadLocalRandom.current().nextDouble()
	
	@JvmStatic
	fun get(max: Int): Int {
		x = x xor (x shr 12)
		x = x xor (x shl 25)
		x = x xor (x shr 27)
		x *= 2685821657736338717L
		
		val factor = abs(x) / Long.MAX_VALUE.toDouble()
		return (max * factor).toInt()
	}
	
	@JvmStatic
	fun get(minRange: Int, maxRange: Int) = minRange + get(maxRange - minRange)
	
	@JvmStatic
	fun get(values: IntArray) = values[get(values.size - 1)]
	
	@JvmStatic
	fun <T> get(values: Array<T>) = values[get(values.size - 1)]
	
	@JvmStatic
	fun <T> get(list: List<T>) = list[get(list.size - 1)]
	
	@JvmStatic val long: Long
		get() = ThreadLocalRandom.current().nextLong()
	
	@JvmStatic
	fun rollDie(maxRoll: Int) = rollDie(maxRoll, 1)
	
	@JvmStatic
	fun rollDie(sides: Int, chance: Int) = get(1, sides) <= chance
	
	@JvmStatic
	fun rollPercent(percent: Int) = get() <= percent * 0.01
	
}