Exercise: Random Picks

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-12-Random-Picks and put the .html solution files for this exercise within it.

The simplest solution to this exercise would be to augment the definition of printSequence() from the Sequence In Range exercise.

Here's the printSequence() function:

function printSequence(a, b, d) {
   if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
      document.write('Nothing to print');
      return;
   }
   for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
      var sep = ', ';
      if (x === a) {
         sep = '';
      }
      document.write(sep + x);
   }
}

In order to return a random integer from the underlying sequence, we just ought to address two cases:

• Return null when the parameters represent an empty/non-existing sequence.
• Return a random element from the constructed list of numbers.

The first case is trivial — return null from the if conditional.

Let's accomplish this right after defining the function randomPick():

function randomPick(a, b, d) {
   if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
      return null;
   }
}

Now, we're only left with the second case, i.e. to return a random element from the constructed list of numbers. This is easy as well.

In printSequence(), we right away print the current item of the sequence. In randomPick(), however, we ought to push it to an array — let's call it nums — and then compute a random integer between 0 and n (exclusive), where n is the length of nums.

This random integer acts as the index of the element of nums to return.

Let's implement this now:

function randomPick(a, b, d) {
   if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
      return null;
   }
   var nums = [];
   for (var x = a; Math.sign(d) * (x - b) < 0; x += d) {
      nums.push(x);
   }
   var randomIndex = Math.floor(Math.random() * nums.length);
   return nums[randomIndex];
}

The randomIndex variable defined here stores a randomly-generated integer, as we discussed above, acting as the index of an element of nums to return. And in the end, this is exactly what's done in line 10.

Let's now test this function on a couple of values:

randomPick(1, 10, 1)

5

randomPick(1, 10, 1)

9

randomPick(1, 10, 1)

1

randomPick(10, 100, 25)

10

randomPick(10, 100, 25)

85

randomPick(10, 10, 25)

null

randomPick(1, 10, -1)

null

And this completes the exercise.

But one question remains to be answered: Is this implementation of randomPick() OK?

No doubt in that the function above always returns back an integer from the underlying sequence (represented by the given parameters); it never makes up values on its own.

However, gaze at the function for a second or two. Does it seem sensible to take the approach that we're taking right now?

In other words, is it wise enough to create a whole list modeling the sequence and only then extract a random element from it? Should we really be doing so?

Well, as it turns out, there is a quick mathematical trick, following from the theory of arithmetic sequences, that we can leverage in implementing randomPick() without generating a list of numbers whatsoever.

Yes, that's right! We can ditch the list completely. Pure math will instead take over and return a random integer from the sequence represented by the three given parameters of randomPick().

Let's appreciate this mathematical trick.

The general form of an arithmetic sequence's ::i^{th}:: term is as follows:

where ::a:: is the initial term and ::d:: is the common difference.

In randomPick(), we are given the maximum integer ::b:: right before which the sequence should end. The formula above and this integer ::b:: are of particular importance.

That is, we use the formula and ::b:: to determine the largest possible value of ::i:: for the sequence, where ::i:: is known to start at ::0::.

In randomPick(), we can then compute a random number between ::0:: and this value of ::i:: (exclusive) and then plug in the ::i:: into the formula above to obtain the corresponding element ::A(i):: of the sequence.

Let's see how to compute this maximum ::i:::

The expression inside the ceil function is obtained by rearranging the formula given above for ::A(i)::. The ceil function is used because ::i:: should be an integer, and it can't be the lesser integer since we need to exclude any value that is equal to ::b::.

Let's accomplish this in randomPick():

function randomPick(a, b, d) {
   if (d === 0 || a === b || (b < a && d > 0) || (a < b && d < 0)) {
      return null;
   }
   var randomIndex = Math.floor(Math.random() * Math.ceil((b - a)  / d));
   return a + d * randomIndex;
}

The Math.ceil() expression is the same as the equation given above. As before, randomIndex represents a random integer denoting the index of an element of the underlying sequence to return.

This element is then computed using randomIndex and the arithmetic sequence's ::i^{th}:: term formula: a + d * randomIndex.

And there you have it; an extremely efficient implementation of randomPick().

See how the list has gone away completely. Now when we call randomPick() with a given set of arguments, there's no memory consumed in generating a list to represent the sequence.

Besides memory, the implementation is even more swift is terms of run time. There is no for loop and no list to iterate over — the random element is picked, more or less, in constant time, by some simple yet beautiful mathematics.