在范围(0 – X)内生成唯一编号,保留历史logging以防止重复

我遇到了挑战,我需要一个函数返回一个给定范围内的随机数从0 - X 不仅如此,我要求返回的数字是唯一的 ; 不要复制以前通过函数返回的数字。

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

怎么会这样做?

你有一些很棒的编程答案。 这里有一个更理想的风味来完成你的全景:-)

你的问题被称为“抽样”或“子集抽样”,有几种方法可以做到这一点。 设N是你抽样框的范围(即, N=X+1 ), M是样本的大小(你想要选取的元素的数量)。

  • 如果NM大得多,那么你需要使用Bentley和Floyd在他的专栏“ 编程珍珠:一个辉煌的样本 ”(这里暂时没有ACM的locking屏幕)中build议的algorithm,我真的推荐这是因为他们明确地给出了代码和散列表等方面的讨论。 那里有几个巧妙的技巧

  • 如果NM处于相同的范围内,那么您可能想要使用Fisher-Yates shuffle,但仅在M步之后停止(而不是N

  • 如果你真的不知道那么Devroye关于随机生成的书的第647页的algorithm是相当快的 。

这应该做到这一点:

 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个随机产生时,它没有任何好的performance – 它在整个列表中search一个空闲的地方。 这个algorithm ,一步一步的Fisher-Yates混洗 ,从问题独特(非重复)随机数在O(1)? ,将performance更好:

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

( 演示 )

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

 // 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的范围 ,似乎运行良好)。 然而; 我不需要一个很大的范围,所以如果你想要产生和追踪一个巨大的范围,那么这个函数可能不适合。

您可以尝试使用当前date和时间值来生成该号码,这将使其唯一。 要在范围内,你可能需要使用一些math函数。