5

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

可选地，完成此操作后（例如，范围已“用尽”），只需返回该范围内的随机数。

怎么做呢？

4

4 回答 4

6

这应该这样做：

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 个随机数时它没有很好的性能 - 它在整个列表中搜索一个空闲位置。这个算法，一步一步的Fisher-Yates 洗牌，来自问题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;
    };
}

（在 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);
        }
    };
}

（演示）

于 2012-08-04T14:24:35.733 回答
3

你得到了一些很棒的编程答案。这是一个更有理论色彩的全景图：-)

您的问题被称为“抽样”或“子集抽样”，您可以通过多种方式做到这一点。让N您作为抽样框架的范围（即N=X+1），并M作为样本的大小（您要选择的元素数量）。

于 2012-08-04T22:16:34.553 回答
2

我写了这个函数。它保留自己的数组和生成数字的历史记录，防止初始重复，如果范围内的所有数字都已输出一次，则继续输出随机数：

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

这是一个工作小提琴

我希望这对某人有用！

编辑：正如下面Pointy所指出的，它可能会在大范围内变慢（这是一个 小提琴，从 0-1000 的范围内，这似乎运行良好）。然而; 我不需要很大的范围，所以如果您希望生成并跟踪一个巨大的范围，那么这个函数可能确实不适合。

于 2012-08-04T12:48:21.593 回答
-1

您可以尝试使用当前日期和时间值生成数字，这将使其独一无二。要使其在范围内，您可能必须使用一些数学函数。

于 2012-08-04T15:23:33.160 回答