Could random unique selection using while cause an infinite loop?

Question

I recently came across code that looked something like this (generates 4 random numbers in an array, this is not the actual code, I just wrote this up now, so it's untested):

var uniqueNumbers = new Array();
var count = 4;
var max = 10;

function main() {
    for (var i = 0; i < count; i++) {

        do {
            var tempNum = Math.floor(Math.random() * max); //number 0-9
        } while (arrayContains(uniqueNumbers, tempNum)) 

        uniqueNumbers.push(tempNum);
    }
}

function arrayContains(a, val) {
    for (var i = 0; i < a.length; i++) {
        if (a[i] == val) return true;
    }
    return false;
}

Is it possible that the while loop could possibly be infinite (or at least take a lot of time)? In the way that it just so happens that we continuously randomly choose a number that happens to be in the array? I imagine the probability of this happening would go up as count increases. It's kind of reminding me of bogosort.

I would think that this would be improved by selecting from a diminishing 'pool' of numbers, instead of selecting randomly, something like:

var uniqueNumbers = new Array();
var count = 4;
var max = 10;
var pool = new Array();

function main() {
    createPool();
    for (var i = 0; i < count; i++) {
        if (var tempNum = selectFromPool()) {
            uniqueNumbers.push(tempNum);
        }
    }
}

function createPool() {
    for (var i = 0; i < max; i++) {
        pool.push(i);
    }
}

function selectFromPool() {
    if (pool.length <= 0) return false;

    var selectedIndex = Math.floor(Math.random() * pool.length);
    var selectedValue = pool[selectedIndex];

    pool = pool.slice(selectedIndex, selectedIndex+1);

    return selectedValue;
}

Is this a better, less fragile way of doing it? Or is there some proof that the while loop will never be infinite because of the pseudo-random nature of computer generated random numbers?

Answer 1

Your first attempt is indeed in danger of getting into an infinite loop if a certain value never gets returned from rand (but any half decent PRNG will return all of them eventually).

Your second attempt is very close to the (most optimal) Fisher-Yates shuffle, with the difference that you use a separate array to store the shuffled result while shrinking the original pool.

Answer 2

It depends on the proportions of count and max, obviously, but most importantly on the behaviour of the random number generator. ECMAScript leaves the behaviour of random() to the implementation, so there's no immediate answer; it would be platform dependent.

Expressed in Python, because it lets me have less fluff around the algorithm, your two algorithms are basically:

def algo1(count, max):
  l=[]
  while len(l)<count:
    x=random.randint(1,max)
    # Might take forever to find an x that fits, particularly if n>m
    if x not in l:
      l.append(x)
  return l

def algo2(count, max):
  choices=range(1,max+1)
  l=[]
  # Python also has random.sample for this operation
  while len(l)<count:
    x=random.choice(choices)  # Can't pick anything in l
    choices.remove(x)         # because it is removed here
    l.append(x)             # also will run out if count>max
  return l

A third algorithm comes to mind which may be useful if random numbers are costly and max is large:

def algo3(count, max):
  assert count<=max
  l=[]
  while len(l)<count:
    x=random.randint(1,max-len(l))
    for y in sorted(l):
      if y<=x:
        x+=1
    l.append(x)
  return l

This version completes in O(n²) time, with limited memory usage and only count random calls. If count>max only the first max elements are randomly ordered; the rest are simply an incrementing series. That's unexpected behaviour, so a guard makes sense.

As for the random number generation itself, that's a rather complex field. The Linux man page for random(3) suggested a book (Numerical Recipes in C: The Art of Scientific Computing) with a chapter on that topic.

A rather infamous example of failing to devise a fair algorithm for this - which also did show the browser dependency in Javascript - is the browser ballot that resulted after a judgement against Microsoft regarding anti-competitive practices in the web browser integration for Windows. Rob Weir's article Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot covers the details, and is an interesting read.

Answer 3

The first method can definitely go into a very long loop, but that is very unlikely to happen. Unless the numbers to pick is not very close to the available numbers, the probability that the loop would be so long that it would be noticable is very small.

If you for example pick 5 numbers out of 10, there is still only a probability of 1 in 1267650600228229401496703205376 that it would go as far as 100 iterations when picking the fifth number.

This is getting into the same range of probability as getting two GUID values that would happen to be the same, and that is considered so unlikely that it in practice never happens.

Still, the second method gives a more predictable performance, so that is preferred unless you would have a huge pool of numbers to pick from. In that case creating the pool would use so much resources that the first method should be considered.