ID:1604987
 
The following is an optimized, efficient, error free Shuffle procedure for lists.

Syntax: Shuffle(var/List)
Code:
proc
Shuffle(list/shuffle)
for(var/i in 1 to shuffle.len) shuffle.Swap(i,rand(1,shuffle.len-1))
return shuffle


Example:
mob/verb
ShuffleList()
var/list/deck = list()
for(var/cardNumber in 1 to 52) deck += cardNumber
deck = Shuffle(deck)
for(var/card in deck) world << card


Zecronious wrote:
Not Efficient

Sorry but I would like it to be noted that this won't give a complete shuffle. Swapping means that some elements might be missed.

In order to get a better shuffle you have to reshuffle it more and more times.

Because of this, it's not actually an efficient shuffle at all.

Incorrect. Unlike your shuffle procedure that randomly picks elements to be removed and readded(In some cases leaving results like 1 and 2 unshuffled; thus proving yours is actually the inefficient procedure. As well as this benchmarking better.) this shuffle procedure loops through the entire length of the array starting at the first element all the way to the last. The only way an element would end up in the same position would be if it's shuffled out of it, then back into it. I'd appreciate if you decided to actually read the code before jumping to split second decisions. Thank you.

In response to D-Cire
D-Cire funny that you should talk about reading code. You didn't read mine. That's not what mine does at all.

Mine makes sure each element has a random place in the list. Not missing one.

Yours swaps elements from left to right with random other elements. That means you might swap a location that's at the end of the list with one at the front. That means that one at the end will never be given a random location.

The spread doesn't give each element a random location, mine does.
Proof:

E is not covered, therefore by contradiction it doesn't cover all elements.



The only way to cover E is to run the process again. The same thing will happen to another element. So on and so forth.
In response to Zecronious
Zecronious wrote:
D-Cire funny that you should talk about reading code. You didn't read mine. That's not what mine does at all.

Mine makes sure each element has a random place in the list. Not missing one.

Yours swaps elements from left to right with random other elements. That means you might swap a location that's at the end of the list with one at the front. That means that one at the end will never be given a random location.

The spread doesn't give each element a random location, mine does.

Ugh, I wish you'd stop acting so arrogant for once and actually just pay attention to your own programming, and others. Actually reading and running through the events of a procedure would help too.

First off, it is what yours does. I'll list your entire proc at the bottom of this post but for now i'll list the exact part im referencing.
for(var/i = 1; i <= givenList.len; i++)

nextElement = rand(1, givenList.len)

In the case of a 52 card deck this evidently equates to "select nextElement as random between 1 and 52". What happens when 1, 2, 3, 4, 5, and 6 are never selected? Yes, you remove and element, and re-add it. I'll take out element 7 and move it to 52. Say thats the first roll, everything then falls down yet 1, 2, 3, 4, 5, and 6 still stay in the EXACT same position. If they're never picked out, they never move. Thus they are missed, and are not random. In fact, they aren't even shuffled.

Now in your attitude towards my code - Did you really just say moving a position doesn't shuffle? Okay, say 52 is now element number 1, and element 1 is 52. Now we select element 2 to swap - the random lens comes out as element 1. Now Element 1 is 2, Element 2 is 52, Element 52 is 1. All the way through. I'll also attach a link to a pastebin of results of mine, and yours.

Please in future threads don't overlook things and try to state your logic as fact without looking at everything. You tried to do it here, and you tried to do it with Ter a few days ago. Both times you were wrong. That should show you something. The arrogant egotistical view on things is doing you no favors.

My Output(Nothing is in the original position): http://pastebin.com/X47dXxdB
Your Output(Some elements haven't changed or been touched): http://pastebin.com/aPkY789P

Your Code:
proc
shuffle(list/givenList)
. = givenList
var/nextElement

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

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

. -= nextElement
. += nextElement

return .


For the hell of it - Benchmarked results at 10,000,000 runs: http://puu.sh/9DzEn/b68fa9a844.png
shuffle is yours.
shuffle2 is mine.

This overall proves mine not only handles thing more efficiently than yours and guarantees a shuffled result while yours has that ability to skip over elements - but mine benchmarks over 200% the speed of yours.
In response to D-Cire
I accidentally left out a -i. You were right that what I thought it did and what it was doing was different. I admit that. Sorry for saying that.


But... Now that I've fixed it. You can't say yours is better. Kind of ironic but my fault.

If you want an explanation... Originally I had two lists. I removed from one and added to the other. People approved that. Then I made it one list but I had to change the mechanics which I didn't stupidly by forgetting to add a "-i".

So yeah, mine is back to beating yours. Good thing I have very thick skin.
What's the deal here, we are looking to ensure all elements move because we're displaying it to a user, and the user has bias?

An unbiased algorithm for shuffling usually permits elements not moving, as that's a valid permutation. But obviously a user sees that result, and feels it isn't 'random' enough, so the user is biased basically, and so we want the algorithm to reflect that bias?
The reason I wrote mine so that it completely shuffles is so that each shuffle is fair and distribution won't lean towards any side.
Well, I can't speak for the implementation above or yours, but it does seem like an implementation that doesn't allow an element to be shuffled back into it's original is by definition biased, against that particular permutation?

Which I mean, may be exactly what's desired. As I just explained, while it's mathematically equally as likely for a given call, that your list should end up in the exact same order it originally in, as it is likely that it ends up in any other particular known permutation ... a human being looking at the shuffled list doesn't see it that way. They are essentially biased, against the original ordering, they don't want to see it.

It's the problem you get with music players apparently "favouring" certain songs, when in practice it's just too unbiased, and an unbiased algorithm is just as likely to pick the same song 3 times in close succession, as it is to not, provided the resulting probabilities across enough picks tend to an even spread.

This is interesting, as it has performance implications. You want it with that bias, when you're say ... giving the user a button that specifically is meant to jumble up a list in a kind of "I don't like this order, show me another one". But that's more costly (not massively, to be fair here).

But you might not care when say, shuffling a big list of mobs to decide the order they'll appear in a tower defence game, as the user doesn't know what the original internal ordering was in the first place.
By way of a for-instance:

proc/zec_shuffle(var/list/givenList)
. = givenList
var/nextElement
for(var/i = 1; i <= givenList.len; i++)
nextElement = rand(1, givenList.len - i)
nextElement = givenList[nextElement]
. -= nextElement
. += nextElement
return .

proc/fisher_yates_shuffle(var/list/L)
var/length = length(L)
if (length < 2)
return L
var/j
for (var/i in 1 to length)
j = rand(i, length)
if (i != j)
L.Swap(i, j)
return L

proc/generate_list(var/length, var/seed, var/upper)
var/list/result = new()
var/i = 0
rand_seed(seed)
while (i < length)
i++
result += rand(upper)
return result

client/verb/Test_Shuffles()
for (var/i in 1 to 10)
var/list/L = generate_list(100000, i, 100000)
zec_shuffle(L)
L = generate_list(100000, i, 100000)
fisher_yates_shuffle(L)


Fisher-Yates is basically unbiased, so it can leave elements in their original places, as that's as probable as moving to any given other position. So it isn't a good pick for our first described scenario, for instance. But the performance difference you get is reasonable, by dropping that requirement:

/proc/zec_shuffle Avg Total CPU: 7.092
/proc/fisher_yates_shuffle Avg Total CPU: 0.081

So you are paying a bit for that biased ordering etc. And of course the usual caveats, that this test scenario is a little unlikely (you don't tend to shuffle such huge lists, the shuffle won't be your bottleneck etc etc)
Well that's a good point, I certainly don't claim my shuffle to be the only shuffle people will ever need. It's a complete shuffle, people might want an incomplete shuffle.

I'm thinking of giving mine a flag for complete or incomplete.
In response to Stephen001
I think that's a fair analysis.
Maybe mine would be better named scattter(/list) as it's like dropping all the elements so they fall randomly.
Or reorder(), as you're guaranteeing a new ordering, where any given element will have a new, random position within the list.
In response to Stephen001
With mine you can end up with the same list.
Oh? Then ... it's not any different in function to Fisher-Yates then, unless I've misunderstood something? I thought yours was specifically ensuring that each element didn't end up in the same position as before.
In response to Stephen001
Must have been a miscommunication.
@Stephen - That's a great point and something that I appreciate pointing out.

@Zecr - You just said in multiple points your procedure is to ensure a new position for each element on a single call of the shuffle? Why are you saying now it's not like that? Also in terms of it being "Better than mine" Evidently they both do the same thing now and results will be similar to how no elements are in the same position unless reshuffled back into it. However, mine still benchmarks at 200%+ of yours. So how can you define yours as "Better"? Mine also has better readability. I feel like your completely overlooking the order in which mine shuffles. Just because the element position being selected will set in a 1 to 52 motion doesn't mean the random can't pick up positions prior to the current index. Thus reshuffling them yet again.

td;lr - Me and Zecr's produce the same randomized results now; difference is benchmark performance shows mine to be 200% more efficient. Although Fisher-Yates' method is faster than both. Lol.
D-Cire, your shuffle is still biased. Fisher-yates has a subtlety you aren't including: the random number to swap with is picked from the elements still not shuffled, not from the entire list.

Here's some test code. For an unbiased shuffle, it'll output about 0.1 for each number. Instead, you'll see a consistent pattern where certain numbers are lower than 0.1 and certain numbers are higher, every time.

proc
Shuffle(list/shuffle)
for(var/i in 1 to shuffle.len) shuffle.Swap(i,rand(1,shuffle.len-1))
return shuffle

mob/verb/test()
var/list/results = list(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
for (var/i in 0 to 1000)
var/list/l = Shuffle(list(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
results[l[1]]++

for (var/i in 1 to 10)
src << "[i]: [results[i] / 1000]"


Changing your shuffle proc to

proc
Shuffle(list/shuffle)
for(var/i in 1 to shuffle.len) shuffle.Swap(i,rand(i,shuffle.len))
return shuffle


fixes that.