我遇到了一个挑战，我需要一个函数来返回一个给定范围内的随机数0 - X。不仅如此，我还要求返回的数字是唯一的；不复制先前调用该函数时已经返回的数字。
或者，当这完成后（例如，范围已“用尽”），只需返回范围内的随机数。
怎么做呢？
在范围 (0 - X) 内生成唯一编号，保留历史记录以防止重复
IT技术
javascript
jquery
arrays
random
2021-01-31 22:07:35
4个回答
这应该这样做：
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 shuffle，来自问题唯一（非重复）随机数在 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 shuffle但仅在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，这似乎运行良好）。然而; 我不需要很大的范围，所以如果您希望生成和跟踪一个很大的范围，这个功能可能确实不适合。
您可以尝试使用当前日期和时间值生成数字，这将使其唯一。为了使其在范围内，您可能需要使用一些数学函数。