在范围（0 - X）内生成唯一编号，保留历史记录以防止重复

I ran into the challenge where I need a function that returns a random number within a given range from 0 - X. Not only that, but I require the number returned to be unique; not duplicating numbers that have already been returned on previous calls to the function.

我遇到了一个挑战,我需要一个函数,在0到X的给定范围内返回一个随机数。不仅如此,我要求返回的数字是唯一的;不复制先前调用该函数时已返回的数字。

Optionally, when this is done (e.g. the range has been 'exhausted'), just return a random number within the range.

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

How would one go about doing this?

怎么会这样做呢?

4 个解决方案

#1

You got some great programming answer. Here's one with a more theoretical flavor to complete your panorama :-)

你有一些很好的编程答案。这是一个更具理论风味的完成你的全景:-)

Your problem is called "sampling" or "subset sampling" and there are several ways you could do this. Let N be the range you are sampling frame (i.e., N=X+1) and M be the size of your sample (the number of elements you want to pick).

您的问题称为“采样”或“子集采样”,您可以通过多种方式执行此操作。设N是采样帧的范围(即N = X + 1),M是样本的大小(要选择的元素数)。

if N is much larger than M, you'll want to use an algorithm such as the one suggested by Bentley and Floyd in his column "Programming Pearls: a sample of brilliance" (temporarily available without ACM's lock screen here), I really recommend this as they explicitly give code and discuss in terms of hash tables, etc.; there a few neat tricks in there

如果N比M大得多,你会想要使用Bentley和Floyd在他的专栏“编程珍珠:一个辉煌的样本”中提出的算法(暂时没有ACM的锁定屏幕),我真的推荐这是因为他们明确地给出代码并讨论哈希表等;那里有一些巧妙的技巧
if N is within the same range as M, then you might want to use the Fisher-Yates shuffle but stop after only M steps (instead of N)

如果N在与M相同的范围内,那么你可能想要使用Fisher-Yates shuffle但只在M步之后停止(而不是N)
if you don't really know then the algorithm on page 647 of Devroye's book on random generation is pretty fast.

如果你真的不知道,那么Devroye关于随机生成的书的第647页上的算法非常快。

#2

This should do it:

这应该这样做:

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

Usage:

var generate = makeRandomRange(20);

var x1 = generate(),
    x2 = generate(),
    ...

Although it works, it has no good performance when the x-th random is generated - it searches the whole list for a free place. This algorithm, a step-by-step Fisher–Yates shuffle, from the question Unique (non-repeating) random numbers in O(1)?, will perform better:

虽然它有效,但是当生成第x个随机数时它没有良好的性能 - 它在整个列表中搜索一个空闲的地方。这个算法,从O(1)?中的唯一(非重复)随机数问题逐步进行Fisher-Yates洗牌,效果会更好:

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

(Demo at jsfiddle.net)

(在jsfiddle.net上演示)

Extended version which does only generate one "group" of unique numbers:

只生成一个唯一数字“组”的扩展版本:

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

(Demo)

#3

I wrote this function. It keeps its own array with a history of generated numbers, preventing initial duplicates, continuing to output a random number if all numbers in the range have been outputted once:

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

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

Here's a working Fiddle

这是一个工作小提琴

I hope this is of use to someone!

我希望这对某人有用!

Edit: as pointed out by Pointy below, it might get slow with a large range (here is a fiddle, going over a range from 0-1000, which seems to run fine). However; I didn't require a very large range, so perhaps this function is indeed not suited if you look to generate and keep track of an enormous range.

编辑:正如下面的Pointy指出的那样,它可能会在很大的范围内变慢(这是一个小提琴,超过0-1000的范围,似乎运行良好)。然而;我不需要非常大的范围,所以如果你想要生成并跟踪一个巨大的范围,这个功能可能确实不适合。

#4

You may try generating the number using the current date and time value which would make it unique. To make it within the range, you may have to use some mathematical function.

您可以尝试使用当前日期和时间值生成数字,这将使其唯一。要使其在范围内,您可能必须使用一些数学函数。

#1