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 回答