"lottery" in javascript - sort algorithm?

Question

I'm trying to understand the code example that's at the end of my post and I need help. So this is supposed to be a "lottery". So here's what I see:

for( i = 1 ; i < 50 ; i++ ){ nums[ i ] = i ; }

Here it assigns the value of i (which will be between 1 and 49) to each each i-th element of the nums array. So I guess it's just making an array that contains the numbers 1 to 49. I don't see the point of this whole line, actually, given the code that follows.

for( i = 1 ; i < 50 ; i++ )
 {
   rand = Math.ceil( Math.random() * 49 ) ;
   temp = nums[ i ] ;
   nums[ i ] = nums[ rand ] ;
   nums[ rand ] =temp ;
 }

---

Here I get confused. So, once again it runs a standard loop from 1 to 49, and for each of the 49 iterations, it:

1. assigns a random number between 1 and 49 to "rand"

2. assigns the i-th value of the 'nums' list (which will still be just i, right?) to temp (why?)

3. assigns the random number to the i-th element of the "nums" array, so presumably if it's at i=1, nums[i] = 1, and now instead of 1 it's the random number.

4. Then it assigns temp (which was the original value, which was i anyway) back to the value that's in the rand-th position of the nums array.

So what am I misunderstanding here? I don't get the point of this. Where is this leading? Am I reading it correctly? Presumably at the end of this, the numbers inside the array are jumbled up, and then at the end it just picks the first six, which are 6 "random" numbers. But why not just do something like:

var nums=[];
for(i=0; i<6; i++) {
  nums[i] == Math.ceil(Math.random() * 49);
} 

along with a test to ensure the random numbers weren't the same?

---

Here's the code example in whole:

function init()
{
 var panel = document.getElementById( "panel" ) ;
 var i , rand , temp , str , nums = [] ;
 for( i = 1 ; i < 50 ; i++ ){ nums[ i ] = i ; }
 for( i = 1 ; i < 50 ; i++ )
 {
   rand = Math.ceil( Math.random() * 49 ) ;
   temp = nums[ i ] ;
   nums[ i ] = nums[ rand ] ;
   nums[ rand ] =temp ;
 }
 str = "Your Six Lucky Numbers:<br>" ;
 for( i = 1 ; i < 7 ; i++ )
 {
   str += nums[ i ] ;
   if( i !== 6 ) { str += " - " ; }
 }
 panel.innerHTML = str;
}
document.addEventListener( "DOMContentLoaded" , init , false ) ;

Answer 1

The code is supposed to create an array of numbers and then shuffle them. It's almost using a Fisher-Yates shuffle, but not quite. There is also a bug in the random number generation.

Putting the numbers 1 through 49 in the array is not pointless, those are the numbers that are used later on. They are not replaced, they are just moved around in the array.

The next loop will shuffle the items in the array, but first let's look at the random number generation. This way of creating a random number is wrong:

rand = Math.ceil(Math.random() * 49); // Don't use this

The Math.random() method returns a value that is 0 <= x < 1. Multiplying that number by 49 and then using Math.ceil doesn't produce numbers between 1 and 49, it produces numbers between 0 and 49. The number 0 comes very rarely, but you can't ignore it. The correct way to produce the random number is:

rand = Math.floor(Math.random() * 49) + 1;

The code for shuffling the items in the array loops through the items and picks an item by random to swap each item with. This produces a biased shuffle, and it should use the Fisher-Yates algorithm instead:

for (i = 49 ; i >= 1 ; i--) {
  rand = Math.floor(Math.random() * i) + 1;
  temp = nums[i];
  nums[i] = nums[rand];
  nums[rand] = temp;
}

The last three lines in the loop swaps two items in the array. It stores away the value from one item, copies the value from the other item into the first, and then puts the stored value in the other item.

(The values of i and rand can actually be the same for some items, so that an item is swapped with itself. This is how the algorithm is supposed to work, it ensures that the item has the same chance of staying in the same place as the chance of being moved to any other place.)

But why not just do something like [code] along with a test to ensure the random numbers weren't the same?

That is another way of creating the random numbers. It would be somewhat more efficient, at least most of the time (it could theoretically loop forever), but it's about the same amount of code.

Another solution would be to put all the numbers in one array, then pick numbers by random from it and move them to another array. That is the same principle as the shuffling algorithm, but it only needs to shuffle enough to get the first six items in the right place (or the last six items as it would be using the Fisher-Yates algorithm). However, removing items from an array is generally an expensive operation, as the items after it needs to be shifted into its place.

Answer 2

It is indeed a basic shuffle. The point is to ensure we only have unique numbers to begin with.

Doing this shuffle iterates once over the loop.

Checking uniqueness requires iterating once over the loop... for every element in the loop.

For small loops like this, the difference is basically nil, but in general when given two options you should take the one that's less computationally complicated... but always remember to comment the code to explain it to future developers!