我遇到了一个挑战,我需要一个函数来返回给定范围内的随机数0 - X
。不仅如此,我还要求返回的数字是唯一的;不重复先前调用该函数时已经返回的数字。
可选地,完成此操作后(例如,范围已“用尽”),只需返回该范围内的随机数。
怎么做呢?
我遇到了一个挑战,我需要一个函数来返回给定范围内的随机数0 - X
。不仅如此,我还要求返回的数字是唯一的;不重复先前调用该函数时已经返回的数字。
可选地,完成此操作后(例如,范围已“用尽”),只需返回该范围内的随机数。
怎么做呢?
这应该这样做:
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;
};
}
仅生成一个“组”唯一编号的扩展版本:
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);
}
};
}
(演示)
你得到了一些很棒的编程答案。这是一个更有理论色彩的全景图:-)
您的问题被称为“抽样”或“子集抽样”,您可以通过多种方式做到这一点。让N
您作为抽样框架的范围(即N=X+1
),并M
作为样本的大小(您要选择的元素数量)。
如果N
比 大得多M
,您将需要使用一种算法,例如 Bentley 和 Floyd 在他的专栏“ Programming Pearls: a sample of brilliance ”中建议的算法(此处暂时没有 ACM 的锁屏),我真的推荐这个为他们明确给出代码并根据哈希表等进行讨论;里面有一些巧妙的技巧
如果N
与 处于同一范围内M
,则您可能希望使用Fisher-Yates 洗牌M
,但仅在步骤后停止(而不是N
)
如果您真的不知道,那么Devroye 关于随机生成的书第 647 页上的算法非常快。
我写了这个函数。它保留自己的数组和生成数字的历史记录,防止初始重复,如果范围内的所有数字都已输出一次,则继续输出随机数:
// 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 的范围内,这似乎运行良好)。然而; 我不需要很大的范围,所以如果您希望生成并跟踪一个巨大的范围,那么这个函数可能确实不适合。
您可以尝试使用当前日期和时间值生成数字,这将使其独一无二。要使其在范围内,您可能必须使用一些数学函数。