0

I'm wondering if some of you understand how the Fisher-Yates shuffle works and can explain it to me. so I found this Fisher-Yates Shuffle code online:

public function Main() {
var tempArray:Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
ShuffleArray(tempArray);
trace(tempArray);
}
public function ShuffleArray(input:Array)
{
for (var i:int = input.length-1; i >=0; i--)
{
var randomIndex:int = Math.floor(Math.random()*(i+1));
var itemAtIndex:Object = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
}

That code works perfectly but I'm still confused

  1. I changed the loop to "input.length" and it doesn't work well, I still got "0" values sometimes. I have no idea why should I use "input.length-1" instead of "input.length"
  2. At the randomize section, why should I randomize the index from 0 to the value (i+1), why don't we just randomize it from 0 to (i) instead?

If some of you understand it, can you please explain it to me? Thank you so much

4
  • You should use length - 1 because arrays are zero based, the first item is [0], but the length is the count of items, starting at 1
    – adeneo
    Jun 27, 2015 at 14:44
  • Ahh I see.. and why should I randomize the index from 0 to (i+1) instead of 0 to (i)?
    – Azkia
    Jun 27, 2015 at 14:46
  • It's just to get a random number, so it's Math.random()*(i+1) and the i+1 part is mainly to not get Math.random() * 0 on the first iteration, which would be 0
    – adeneo
    Jun 27, 2015 at 14:48
  • But the after declaring it with length -1, the "i" value would be = "9" right? and if I use Math.random()*(i), it would be Math.random()*(9) and I won't get "0" value. And if use Math.random()*(i+1), it would be Math.random()*(10), I won't get "0" either. So.. I think there won't be any differences if I use the Math.random * (i) instead of Math.random * (i +1)??
    – Azkia
    Jun 27, 2015 at 14:59

2 Answers 2

0
  1. Js's array index starts at 0, so array a with length n 's last element is a[n -1].

  2. Math.random return a value from 0 to 0.9999...., but not include 1(range at [0, 1)), so Math.random()* (i + 1), would have a value from 0 to i + 0.999999......, but not i + 1(range [0, i+1)), and use Math.floor to cut the dot parts to get a Integer, so we get a number in range [0, i].

0

let me explain with an example with negation lets says the array size is 10.

1)if we use index.length line 3 in the for loop will read

input[randomIndex] = input[i] i.e.
input[randomIndex] = input[10];

but since javascript has 0 based arrays ,it has values from index 0 to 9 .index 10 will be out of bounds .Hence we should shuffle from last element(index 9 only)

2)for your second question if we use i instead of i+1. lets say you are in the 1st iteration of the loop for index 9(will hold true for other iterations also). Here i is 9 as seen above .we want 9th index to be shuffled from any one of the indices from 0 to 9 Math.random will return from 0 to .999 and Math.floor will lower bound it so in our case,maximum value will be .999 * (9+1) = 9.99 .Math.floor will lower bound it to 9.So range is [0,9]

incase we used i maximum possible value would be 8 i.e, Range[0,8]

Hence we use i+1 since we want values from [0,9]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.