[General] Shuffle

[Chaosy]

So, I am in need of shuffling an array of numbers.
loop 1-max
temp = array;
rng = random between i-max
array = array[rng]
array[rng] = temp

Somehow this does not seem like a 'shuffle' to me.
Not to mention at the end, theoretically, nothing has changed. ( sure the chance of that happening is small but you get my point x) )
I could work around this issue with extra code, but I feel like it's getting more complex than it should at that point.

 

[Deleted member 219079]

When choosing rng, you have to close out the current index i.

 

[Chaosy]

By "close out" you mean:
if(rng != i) ?

 

[Deleted member 219079]

If your pseudo code would translate into this:

local integer i = 0
local integer j
local <type> swap
loop
    exitwhen i == maxIndex
    set j = GetRandomInt(i, maxIndex) // change this to GetRandomInt(i+1, maxIndex)
    set swap = myArray[i]
    set myArray[i] = myArray[j]
    set myArray[j] = swap
    set i = i+1
endloop

Edit: Fixed code (comment below).

 

[Aniki]

If your pseudo code would translate into this:

local integer i = 0
local integer j
local <type> swap
loop
    exitwhen i == maxIndex
    set j = GetRandomInt(i, maxIndex) // change this to GetRandomInt(i+1, maxIndex)
    set swap = myArray[i]
    set myArray[i] = myArray[j]
    set myArray[j] = swap
    set i = i-1
endloop

Assuming you meant set i = i + 1 (otherwise you will read myArray[-1]), changing:

set j = GetRandomInt(i, maxIndex)
// to
set j = GetRandomInt(i + 1, maxIndex)

means that the 0th element will never be shuffled so some permutations will never be generated.

 

[Deleted member 219079]

Yes, stupid mistake.

What do you mean 0th element is never shuffled?

 

[Aniki]

What do you mean 0th element is never shuffled?

"Some permutations will never be generated."

 

[Deleted member 219079]

But j is the destination place. Changing low bound of range from i to i+1 specifically means that the 1st element is guaranteed to have switched places. Therefore it's not possible for the array not to have changes, which is what Chaosy wanted.

 

[Aniki]

Lets say myArray = [0: X, 1: A, 2: B]
maxIndex = 2
i starts from 0 and goes to maxIndex - 1 (exitwhen i == maxIndex)
i.e we will have 2 iterations (1st i = 0, 2nd: i = 1)

on the 1st iteration (i = 0)
j = 1 or 2 (GetRandomInt( i + 1 = 1, maxIndex=2 ))

when j = 1 myArray = [0: A, 1: X, 2: B]
when j = 2 myArray = [0: B, 1: A, 2: X]

on the 2nd iteration (i = 1)

j = 2 ((GetRandomInt( i + 1 = 2, maxIndex=2 ))

when j = 2
    and myArray = [0: A, 1: X, 2: B], myArray = [0: A, 1: B, 2: X]
    and myArray = [0: B, 1: A, 2: X], myArray = [0: B, 1: X, 2: A]

I.e X will never end up in the 0th slot.

 

[Deleted member 219079]

the 1st element is guaranteed to have switched places

This is exactly what Chaosy wanted; a way to enforce that the order doesn't stay the same.

 

[Aniki]

This is exactly what Chaosy wanted; a way to enforce that the order doesn't stay the same.

He did say:

So, I am in need of shuffling an array of numbers.

I am assuming he wants the shuffling to produce any of the possible arrangements of the numbers
with equal probability, and my point was that your suggested change results into an algorithm that cannot
generate all the permutations, i.e some are much more likely than others. It's not the end of the world of course but still...

 

[Deleted member 219079]

Okay?