为了账号安全,请及时绑定邮箱和手机立即绑定

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

/ 猿问

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

繁花不似锦 2019-12-06 15:08:29

在遇到挑战时,我需要一个函数,该函数返回从到给定范围内的随机数0 - X。不仅如此,我还要求返回的数字必须唯一;不重复在先前对该函数的调用中已返回的数字。

(可选)完成此操作后(例如,范围已“用尽”),只需返回该范围内的随机数即可。

人们将如何去做呢?


查看完整描述

3 回答

?
qq_花开花谢_0

应该这样做:


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)中的唯一(非重复)随机数问题开始的分步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;

    };

}

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

        }

    };

}


查看完整回答
反对 回复 2019-12-06
?
拉莫斯之舞

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

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

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

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

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


查看完整回答
反对 回复 2019-12-06
?
蛊毒传说

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


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


查看完整回答
反对 回复 2019-12-06

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信