Shuffle proc

Page: 1 2
ID:1598267
 
Jun 13 2014, 2:59 am (Edited on Jun 16 2014, 2:09 am)
I found a shuffle proc here but I think mine might be better. I think mine is a bit more intuitive, as it makes use of the built-in procs instead of swapping indexes as they would teach you to swap variables passed by reference in a CS class.

    Shuffle(var/list/L)
        var/iters = 4 * L.len
/* The number of iterations isn't terribly important, as long as it's sufficiently large.
For larger data sets, you will need larger iterations. */
        var/i1 = 0 // index to swap
        var/i2 = 0 // index to swap
        while(iters)
            i1 = rand(1, L.len)
            i2 = rand(1, L.len)
            L.Swap(i1, i2) // swaps indexes
            iters -- // loop counter down.


Note: I store these sorts of procs as global procs, this is easily moved into a mob.Shuffle() proc or something.
Jun 13 2014, 6:09 am
If you're interested in furthering your CS knowledge I suggest this challenge:

What you should make is a realistic shuffling proc if you're dealing with cards. If I remember correctly my grandmother would shuffle five times before each hand with a cut between each shuffle. Assume shuffling interlaces cards from the top half of the cards and the bottom half of the cards and that cuts always happen right down the middle and swap the top and bottom halves of the deck.

Make it by only doing procedures on the list passed in, you can assume that there will always be an even number of elements.
Jun 13 2014, 6:57 am
I can't say I understand the problem. Could you go over what a "shuffle" and a "cut" are?
Jun 13 2014, 1:16 pm
I believe he just means a realistic shuffle and cut.

Shuffling would just be swapping card locations with one another and cutting it would be removing half of the deck to form two decks, and then swapping it so the bottom is now on top and such.
Jun 13 2014, 1:19 pm
Just for a semi visual

This is my deck of cards, initially

1,2,3,4,5,6


We shuffle them.

2,4,1,3,5,6


Cut the deck down the middle

2,4,1 //deck 1

3,5,6 //deck 2


swap the two locations so the bottom is now on top.

3,5,6,2,4,1


Then repeat the process perhaps 2 more times, or this would do.

I believe this was what he was trying to say though.
Jun 13 2014, 3:13 pm
Correct except your shuffling process should end up looking like this:

before
1,2,3,4,5,6


after
1,4,2,5,3,6
Jun 13 2014, 3:15 pm
Yeah haha
Jun 13 2014, 3:36 pm
This is actually quite tricky if you're not allowed to instantiate new lists.
Jun 13 2014, 3:58 pm
Took a little thought, but this will do a shuffle and a cut without instantiating a new list and with a complexity of O(N)

proc/Shuffle(list/List)
    for(var/i = List.len/2+1, i<=List.len*1.5, i++)
        if(i>List.len)
            List.Swap(i-List.len,i-List.len/2)
        else
            List.Insert((i-List.len/2)*2, List[i])
            List.Cut(i+1,i+2)
Jun 13 2014, 8:08 pm
Look, here's a proper shuffling proc. You're all making this way more complicated than it should be.

All you need to do is take out a random element from the given array and add it to an empty array.

How are you guys getting ideas like 40,000 iterations and splitting? Am I the only person gob smacked by this?

proc
    shuffle(list/givenList)
        var/list/finalList[givenList.len]
        var/nextElement

        for(var/i = 1; i <= finalList.len; i++)

            nextElement = rand(1, givenList.len)
            nextElement = givenList[nextElement]

            finalList[i] = nextElement
            givenList.Remove(nextElement)

        return finalList


How to use it:
mob
    Login()
        var/list/L = list("a","b","c","d")
        L = shuffle(L)

        for(var/i = 1; i <= L.len; i++)
            world << "\[[L[i]]]"
        ..()
Jun 13 2014, 8:13 pm
In response to Zecronious
Yes, this shuffles but doesn't cut. The whole point was to make it cut as well.
Jun 13 2014, 8:14 pm
40000 iterations comes from my experience in finding Lyapnuov exponents for certain maps. You iterate a map 40000 times, cut out the first 20000 elements (so the transient behavior has passed) and analyze the rest.
Jun 13 2014, 8:16 pm
In response to Ssj4justdale
Why is the cut important?
Jun 13 2014, 8:24 pm
In response to Lugia319
That still doesn't explain to me why you're using an extraordinary amount of iterations to shuffle.

Your topic is set up like you're given people code to shuffle things with when it's grossly inefficient and no one should ever use it to shuffle with.

Jun 13 2014, 8:27 pm
Shuffle iterations changes based on the length of the list. I deal with lists that are 10000 elements long so I used 40000. If you're dealing with 100 element lists you could get away with 300 or 400.
Jun 13 2014, 8:43 pm
In response to Lugia319
Your code makes people who use do the guess work in their heads for every list they give it. Do you see how bad that is? My shuffle will do the appropriate amount of iterations no matter what size list it's given.

With yours people will end up doing either way too many iterations or not enough iterations.
Jun 13 2014, 8:53 pm
There's no such thing as shuffling too much unless you're worried about memory which for the size of BYOND games isn't a problem. Though I'd be interested in the memory use of your code in larger lists. I might do some comparing after I finish making videos.
Jun 13 2014, 9:01 pm
In response to Zecronious
Zecronious wrote:
Your code makes people who use do the guess work in their heads for every list they give it. Do you see how bad that is? My shuffle will do the appropriate amount of iterations no matter what size list it's given.

With yours people will end up doing either way too many iterations or not enough iterations.

Yours also makes a new instantiated list; something they were trying to avoid entirely. As for the "Cut" That was simply added by Oasis as a challenge in order to try to figure something out - Again, without instantiating a new list.

On top of this I've yet to see anyone state that any of these were the most efficient way to program a shuffle proc. Lugia was also stating he thinks his proc is an improvement to the one he found, that he linked to and again, not the most efficient way. However you came in here with a seemingly hostile attitude and started commenting without ever taking the time to grasp the initial concept of the post itself.

As for the last thing you said it isn't hard to just make the iteration's auto-generate as 3-4 times the size of the list considering that is the reoccuring pattern I see lugia using as his number of iterations anyway.
Jun 13 2014, 9:33 pm
In response to D-Cire
This is tutorials and snippits. It's where you put things for other people to use. And yes of course my attitude seems hostile because I can't believe my eyes that Lugia put this here for other people to use. It's a really bad example of how to write a shuffle process.

Yes I use a new list but that's what makes mine work so effectively.
Jun 13 2014, 9:38 pm
Here, I took out the extra list and it still works fine.

proc
    shuffle(list/givenList)
        var/nextElement
        
        for(var/i = 1; i <= givenList.len; i++)
            
            nextElement = rand(1, givenList.len)
            nextElement = givenList[nextElement]
            
            givenList.Remove(nextElement)
            givenList.Add(nextElement)

        return givenList


That's a fully optimized, fully functional, completely effective shuffle.

Something people should use, something that should be in tutorials and snippits, not this snippit by Lugia.
Page: 1 2