产生范围内的唯一号码（0 - X），保持记录，防止重复(Generate unique numb

我遇到了，我需要从返回给定范围内的随机数的函数的挑战0 - X 。不仅如此，但我需要返回的数字是唯一的 ; 没有复制一个已经在以前的调用该函数返回的数字。

可选的，当这样做（例如，范围已经“筋疲力尽”），只是范围内返回一个随机数。

如何将一个去这样做呢？

Answer 1:

这应该这样做：

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个随机产生的时候 - 它会搜索一个自由的地方整个列表。该算法中，步骤一步费雪耶茨洗牌，从提问唯一（非重复）的随机数在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);
        }
    };
}

（演示）

Answer 2:

你有一些伟大的编程答案。这里有一个具有更多的理论味来完成你的全景:-)

你的问题被称为“采样”或“子采样”，有几种方法可以做到这一点。让N是你正在采样帧（即，范围N=X+1 ）和M是您的样品（你想选择的元素的数目）的尺寸。

如果N远远大于M ，你要使用的算法，如一个在他的专栏由宾利与弗洛伊德提出“ 编程珠玑：辉煌的样本 ”（不ACM的锁屏界面暂时可用在这里），我真的建议这一点，也明确给出代码，并在哈希表等方面的讨论; 在那里有一些巧妙的技巧
如果N是相同的范围内， M ，那么你可能想使用费雪耶茨洗牌，但只有在停止M的步骤（而不是N ）
如果你真的不知道，然后对算法Devroye的书上随机生成的647页是非常快的。

Answer 3:

我写了这个功能。它保持它自己的阵列生成的数字的历史，防止初始重复，继续输出的随机数，如果在该范围内的所有数字都被输出一次：

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

这里有一个工作的小提琴

我希望这是使用的人！

编辑：如指出尖尖的下面，它可能会得到一个大范围的缓慢（在这里是一个小提琴，会在一定范围内，从0-1000 ，这似乎运行正常）。然而; 我并不需要一个非常大的范围内，所以也许这个功能确实不适合，如果你看看生成和保持的非常广的轨道。