Thread: [Kotlin] Random Permutation

Page 1 of 6 123 ... LastLast
Results 1 to 10 of 52
  1. #1 [Kotlin] Random Permutation 
    Community Veteran


    Join Date
    Dec 2008
    Posts
    4,264
    Thanks given
    405
    Thanks received
    432
    Rep Power
    1684
    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
    	
    }
    Reply With Quote  
     

  2. Thankful user:


  3. #2  
    Registered Member
    Join Date
    Jul 2014
    Posts
    54
    Thanks given
    6
    Thanks received
    4
    Rep Power
    0
    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?
    Reply With Quote  
     

  4. #3  
    Community Veteran


    Join Date
    Dec 2008
    Posts
    4,264
    Thanks given
    405
    Thanks received
    432
    Rep Power
    1684
    Quote Originally Posted by X_Twinz1994 View Post
    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.
    Reply With Quote  
     

  5. #4  
    Banned

    Join Date
    Jun 2010
    Age
    23
    Posts
    4,832
    Thanks given
    1,673
    Thanks received
    1,558
    Rep Power
    0
    Good use of extension functions =]. I'd work on your unit tests though!
    Reply With Quote  
     

  6. #5  
    Renown Programmer

    Bartvh's Avatar
    Join Date
    May 2017
    Posts
    371
    Thanks given
    86
    Thanks received
    202
    Rep Power
    477
    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.
    Reply With Quote  
     

  7. Thankful users:


  8. #6  
    Community Veteran


    Join Date
    Dec 2008
    Posts
    4,264
    Thanks given
    405
    Thanks received
    432
    Rep Power
    1684
    Quote Originally Posted by Bartvh View Post
    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.
    Last edited by Gluon; 01-15-2021 at 12:01 AM.
    Reply With Quote  
     

  9. Thankful user:


  10. #7  
    Registered Member
    Velocity's Avatar
    Join Date
    Jan 2009
    Age
    25
    Posts
    2,029
    Thanks given
    1,013
    Thanks received
    2,373
    Rep Power
    4112
    Quote Originally Posted by Bartvh View Post
    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
    xxxxxxx
    Reply With Quote  
     

  11. Thankful users:


  12. #8  
    Community Veteran


    Join Date
    Dec 2008
    Posts
    4,264
    Thanks given
    405
    Thanks received
    432
    Rep Power
    1684
    Quote Originally Posted by Tyluur View Post
    Good use of extension functions =]. I'd work on your unit tests though!
    How could they be improved?
    Reply With Quote  
     

  13. #9  
    Banned

    Join Date
    Jun 2010
    Age
    23
    Posts
    4,832
    Thanks given
    1,673
    Thanks received
    1,558
    Rep Power
    0
    Quote Originally Posted by Gluon View Post
    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.
    Reply With Quote  
     

  14. #10  
    Registered Member
    Velocity's Avatar
    Join Date
    Jan 2009
    Age
    25
    Posts
    2,029
    Thanks given
    1,013
    Thanks received
    2,373
    Rep Power
    4112
    Quote Originally Posted by Gluon View Post
    How could they be improved?
    by converting them into Perl
    xxxxxxx
    Reply With Quote  
     

Page 1 of 6 123 ... LastLast

Thread Information
Users Browsing this Thread

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


User Tag List

Similar Threads

  1. Some Random Events
    By Eleclion in forum Tutorials
    Replies: 4
    Last Post: 05-15-2007, 11:38 PM
  2. Guardian Random Events
    By Eleclion in forum Tutorials
    Replies: 3
    Last Post: 05-12-2007, 08:21 PM
  3. Some Random S**t
    By Darklordants Evil Bro in forum Showcase
    Replies: 2
    Last Post: 04-13-2007, 09:42 PM
  4. A few Random Renders...
    By oblak10 in forum General
    Replies: 2
    Last Post: 04-02-2007, 04:31 AM
  5. my latest sigs :D and random GFX
    By Oblak Lol in forum Showcase
    Replies: 10
    Last Post: 03-31-2007, 10:41 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •