javascript - 生成范围 (0 - X) 内的唯一编号，保留历史记录以防止重复

Question

我遇到了一个挑战，我需要一个函数来返回 0 - X 给定范围内的随机数。不仅如此，我还要求返回的数字是唯一的；不复制先前调用该函数时已经返回的数字。

可选择地，当这完成时(例如，范围已“用尽”)，只需返回范围内的随机数。

人们会怎么做呢？

Answer 1

应该这样做:

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;
        }
    };
}

用法:

var generate = makeRandomRange(20);

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

---

虽然它有效，但是当生成第 x 个随机数时它没有很好的性能 - 它会在整个列表中搜索一个空闲位置。 This algorithm ，一步一步Fisher–Yates shuffle ，来自问题 Unique (non-repeating) random numbers in O(1)? , 会表现得更好:

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 )

只生成一组“唯一”数字的扩展版本:

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 )