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

Question

在遇到挑战时，我需要一个函数，该函数返回从到给定范围内的随机数0 - X。不仅如此，我还要求返回的数字必须唯一；不重复在先前对该函数的调用中已返回的数字。（可选）完成此操作后（例如，范围已“用尽”），只需返回该范围内的随机数即可。人们将如何去做呢？

Answer 1

您得到了一些很棒的编程答案。这是一种更具理论色彩的全景图：-)

您的问题称为“采样”或“子集采样”，您可以通过几种方法来执行此操作。让N是你所抽样框的范围内（即N=X+1），并M为您的样品（你想挑元素的数量）的大小。

• 如果N比更大M，您将要使用一种算法，例如Bentley和Floyd在他的专栏“ Programming Pearls：辉煌的示例 ”中建议的算法（此处暂时不带ACM的锁定屏幕而提供），我真的推荐这样做他们明确给出代码并根据哈希表等进行讨论；那里有一些整洁的花样

• 如果N与处于同一范围内M，则您可能需要使用Fisher-Yates随机播放，但仅需M一步即可停止（而不是N）

• 如果您真的不太了解，那么Devroye关于随机生成的书第647页上的算法非常快。

Answer 2

我写了这个功能。它使用生成的数字的历史记录保留其自己的数组，防止初始重复，如果范围内的所有数字均已输出一次，则继续输出随机数：

// 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的范围内运行，似乎运行良好）。然而; 我并不需要很大的范围，所以如果您希望生成并跟踪很大的范围，则此功能可能确实不适合。