Generate unique number within range (0 - X), keeping a history to prevent duplicates

Question

I ran into the challenge where I need a function that returns a random number within a given range from 0 - X. Not only that, but I require the number returned to be unique; not duplicating numbers that have already been returned on previous calls to the function.

Optionally, when this is done (e.g. the range has been 'exhausted'), just return a random number within the range.

How would one go about doing this?

Answer 1

This should do it:

function makeRandomRange(x) {
    var used = new Array(x),
        exhausted = false;
    return function getRandom() {
        var random = Math.floor(Math.random() * x);
        if (exhausted) {
            return random;
        } else {
            for (var i=0; i<x; i++) {
                random = (random + 1) % x;
                if (random in used)
                    continue;
                used[random] = true;
                return random;
            }
            // no free place found
            exhausted = true;
            used = null; // free memory
            return random;
        }
    };
}

Usage:

var generate = makeRandomRange(20);

var x1 = generate(),
    x2 = generate(),
    ...

---

Although it works, it has no good performance when the x-th random is generated - it searches the whole list for a free place. This algorithm, a step-by-step Fisher–Yates shuffle, from the question Unique (non-repeating) random numbers in O(1)?, will perform better:

function makeRandomRange(x) {
    var range = new Array(x),
        pointer = x;
    return function getRandom() {
        pointer = (pointer-1+x) % x;
        var random = Math.floor(Math.random() * pointer);
        var num = (random in range) ? range[random] : random;
        range[random] = (pointer in range) ? range[pointer] : pointer;
        return range[pointer] = num;
    };
}

(Demo at jsfiddle.net)

Extended version which does only generate one "group" of unique numbers:

function makeRandomRange(x) {
    var range = new Array(x),
        pointer = x;
    return function getRandom() {
        if (range) {
            pointer--;
            var random = Math.floor(Math.random() * pointer);
            var num = (random in range) ? range[random] : random;
            range[random] = (pointer in range) ? range[pointer] : pointer;
            range[pointer] = num;
            if (pointer <= 0) { // first x numbers had been unique
                range = null; // free memory;
            }
            return num;
        } else {
            return Math.floor(Math.random() * x);
        }
    };
}

(Demo)

Answer 2

You got some great programming answer. Here's one with a more theoretical flavor to complete your panorama :-)

Your problem is called "sampling" or "subset sampling" and there are several ways you could do this. Let N be the range you are sampling frame (i.e., N=X+1) and M be the size of your sample (the number of elements you want to pick).

• if N is much larger than M, you'll want to use an algorithm such as the one suggested by Bentley and Floyd in his column "Programming Pearls: a sample of brilliance" (temporarily available without ACM's lock screen here), I really recommend this as they explicitly give code and discuss in terms of hash tables, etc.; there a few neat tricks in there

• if N is within the same range as M, then you might want to use the Fisher-Yates shuffle but stop after only M steps (instead of N)

• if you don't really know then the algorithm on page 647 of Devroye's book on random generation is pretty fast.

Answer 3

I wrote this function. It keeps its own array with a history of generated numbers, preventing initial duplicates, continuing to output a random number if all numbers in the range have been outputted once:

// Generates a unique number from a range
// keeps track of generated numbers in a history array
// if all numbers in the range have been returned once, keep outputting random numbers within the range
var UniqueRandom = { NumHistory: new Array(), generate: function(maxNum) {
        var current = Math.round(Math.random()*(maxNum-1));
        if (maxNum > 1 && this.NumHistory.length > 0) {
            if (this.NumHistory.length != maxNum) {
                while($.inArray(current, this.NumHistory) != -1) { current = Math.round(Math.random()*(maxNum-1)); }
                this.NumHistory.push(current);
                return current;
            } else {
                //unique numbers done, continue outputting random numbers, or we could reset the history array (NumHistory = [];)
                return current;
            }
        } else {
            //first time only
            this.NumHistory.push(current);
            return current;
        }
    }
};

Here's a working Fiddle

I hope this is of use to someone!

Edit: as pointed out by Pointy below, it might get slow with a large range (here is a fiddle, going over a range from 0-1000, which seems to run fine). However; I didn't require a very large range, so perhaps this function is indeed not suited if you look to generate and keep track of an enormous range.