# Thread: [Kotlin] Random Permutation

1. 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

}``````  2. ## Thankful user:

3. You said it works like shuffling a deck of cards, i could use this system for a Box Opening and picking random items to reward?  4. Originally Posted by X_Twinz1994 You said it works like shuffling a deck of cards, i could use this system for a Box Opening and picking random items to reward?
Yup.  5. Good use of extension functions =]. I'd work on your unit tests though!  6. Most of your tests are useless. Also, why do you use 2 different random variables (SecureRandom and ThreadLocalRandom)?
Also, this won't work for PID shuffling. Because the PID has to be the same for a set amount of ticks. In your implementation you will get a different randomized iteration every time you call doLoop.
For PID it is far more efficient and easier to just maintain an ordered list and shuffle that every x amount of ticks.
Aslo, finding a random player inside a region can be done in O(1) time without iterating by just accessing your data with random index.
Similarly, spawning bosses in random order can just be done by adding a random spawn delay.

If you want to iterate over a data structure in random order it is probably better to just call [Only registered and activated users can see links. ] and then do normal iteration.  7. ## Thankful users:

8. Originally Posted by Bartvh Most of your tests are useless. Also, why do you use 2 different random variables (SecureRandom and ThreadLocalRandom)?
Also, this won't work for PID shuffling. Because the PID has to be the same for a set amount of ticks. In your implementation you will get a different randomized iteration every time you call doLoop.
For PID it is far more efficient and easier to just maintain an ordered list and shuffle that every x amount of ticks.
Aslo, finding a random player inside a region can be done in O(1) time without iterating by just accessing your data with random index.
Similarly, spawning bosses in random order can just be done by adding a random spawn delay.

If you want to iterate over a data structure in random order it is probably better to just call [Only registered and activated users can see links. ] and then do normal iteration.

#1 This is a legacy code base that initially used ThreadLocalRandom, that method has since been removed.

#2 You would only shuffle your pids when you need it. No one said anything about shuffling pids every tick. If you use this to shuffle pids every tick you have no idea what you're doing. Keeping a list and shuffling it every x ticks is 100% slower than the code above. The code above is always O(1) where your method first needs to clone a list, add all the contents in a random order, then you finally get the O(1) you speak of.

#3 calling shuffled creates an unnecessary allocation. Any allocation is more expensive than what my code does above. If you have a server with thousands of players and you're unnecessarily creating allocations for shuffling pids, spawns, random rewards, etc it will be much slower than what I've posted.

Also how could the unit tests be improved? To me it seems every use case is tested and made sure functionality is working.  9. ## Thankful user:

10. Originally Posted by Bartvh Most of your tests are useless. Also, why do you use 2 different random variables (SecureRandom and ThreadLocalRandom)?
Also, this won't work for PID shuffling. Because the PID has to be the same for a set amount of ticks. In your implementation you will get a different randomized iteration every time you call doLoop.
For PID it is far more efficient and easier to just maintain an ordered list and shuffle that every x amount of ticks.
Aslo, finding a random player inside a region can be done in O(1) time without iterating by just accessing your data with random index.
Similarly, spawning bosses in random order can just be done by adding a random spawn delay.

If you want to iterate over a data structure in random order it is probably better to just call [Only registered and activated users can see links. ] and then do normal iteration.
it isn't "far more efficient" without proof. and yes this works perfectly fine for pid shuffling because the whole point of pid shuffling is to NOT get 5 ticks of the same pid; that gives player A an edge over B up to 4 ticks if the duel match starts at the correct time, just after the shuffle.

was this your dissertation? been a while since I've seen someone go balls deep on a snippet topic lol  11. ## Thankful users:

12. Originally Posted by Tyluur Good use of extension functions =]. I'd work on your unit tests though!
How could they be improved?  13. Originally Posted by Gluon How could they be improved?
Code:
`````` @[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))``````
I would've used one function to test for a dynamic array randomization.  14. Originally Posted by Gluon How could they be improved?
by converting them into Perl  Thread Information
##### Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

## User Tag List

 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Forum Rules