js随机数生成器的扩展0.前言1.扩展+分区2.二进制法3. 总结

0.前言

给你一个能生成随机整数1-7的函数,就叫他生成器get7吧,用它来生成一个1-11的随机整数,不能使用random,而且要等概率。

getx就是指一个能生成1到x的随机数的函数

主角:get7(你们所有人都没有random这个技能,全都disable了)

function  get7() {
	return ~~(Math.random()*7)+1 //规则:整篇文章,唯一能用random的地方
}
复制代码

1.扩展+分区

既然是扩展,那么我给小范围随机数生成器扩展个几倍,再截取目标随机数范围不就得了。 先问一下,怎么用get7能实现一个合格的get14?这样子?

function get14(){
	return get7() +get7() 
}
复制代码

我们来测试一下:

    	var obj = Object.create(null)
    	for(var i = 0;i<1000000;i++){
    		var n = get14();
    		if(!obj[n]){
    			obj[n] = 1
    		}else{
    			obj[n] ++
    		}
    	}
    	console.log(obj)
复制代码

先不说最小值的问题,首先,他不是等概率的序列 那么我们探讨另一个问题,究竟get14能不能直接用get7加减乘除就表示出来?

喂,说get7() 乘以11/7的那个,你确定没问题?

1.1 扩展

既然是小范围随机扩展到大范围,那么肯定离不开小范围随机数生成器get7的多次调用。当然我们最终目标很明确,目标随机数生成器get11,它的每一个随机数都会等概率映射到get7的扩展序列里面:

然后我们很快就可以想到一个公式:

a*(getx - 1) + getx
复制代码

a是个整数,整个公式含义是,把getx扩展为a倍,并且实现等概率分布。比如x是3,我们想扩展成2倍,a=2,就是2*(get3 - 1) + get3,范围是1-7,但是,我们看看概率:

 x\y   1  2  3
  0    1  2  3 
  2    3  4  5
  4    5  6  7   =》1-7的概率是1:1:2:1:2:1:1
复制代码

明显这个公式还有前提

1.2 a取值范围

我们再看a = 1:

x\y 1  2  3
 0  1  2  3 
 1  2  3  4
 2  3  4  5   =》1-5的概率是1:2:3:2:1
复制代码

好像矩阵每一行都是有交集

//如果a是3,ran3 - 1生成0-6 ,ran3 生成 1-3
x\y  1  2  3
0  1  2  3 
3  4  5  6
6  7  8  9   =》1-9等概率

//如果a是4,ran3 - 1生成0-8 ,ran3 生成 1-3
x\y 1  2  3
0  1  2  3 
4  5  6  7
8  9  10 11   =》数字都是等概率出现的,只是中间缺失了一些数,但不影响大局
复制代码

所以,只要保证所有的数等概率出现,先满足映射表最大值大于等于自身的平方(3*3 = 9,即a至少要是3) 为什么呢?因为不足本身,必然有交集,就像上面1和2两个矩阵每一行都有交集,只要大于本身的大小,矩阵每一行就不会有交集,没有交集,那它们就可以等概率 所以,对于7想扩展一个等概率序列,get14(get小于49都是没用,不是等概率)显然是没用的,起码要get49,此后所有的序列长度都是49。所以一个get14得通过get49得到,我们也可以从get49到get11了

1.3 从get49到get11

function get49(){
    var n = 7*(get7()-1) + get7() //a*(getx - 1) + getx,a取7,不信自己打印看一下
    return  n
}
var obj = Object.create(null)
for(var i = 0;i<1000000;i++){
	var n = get49();
	if(!obj[n]){
		obj[n] = 1
	}else{
		obj[n] ++
	}
}
console.log(obj)
复制代码

既然我们看见全部元素等概率出现了,那我们只要把多余的排除掉就行,即是遇到不是我们想要的范围那些,重新生成一次。

function get11(){
    var n = 7*(get7()-1) + get7() //a*(getx - 1) + getx,a取7,不信自己打印看一下
    return  n > 11?get11():n
}
复制代码

改改get49就行,对了,好像扩展数组太多没用的了,我们应该提高扩展数组的利用率,并且减小递归次数

function get11(){
	var n = 7*(get7()-1) + get7() 
	return  n>44?get11():~~((n-1) / 4)+1
}
复制代码

2.二进制法

对小随机数函数进行二进制划分,一半表示1一半表示0,然后用二进制表示大随机数,再去除多余的 get7到get11,8<11<16,我们取4位二进制,也就是取4次get7 因为7是奇数,我们就去掉一个吧,那我们去掉1,当遇到1重新生成一次,剩下的划分二等分

//获取二进制序列
function getBinary(){
	var n = get7()
	if(n>4){
		return 1
	}else if(n>1){
		return 0
	}else{
		return getBinary()
	}
}
//二进制序列转化回去
function get11_by_binary(){
	var res = ''
	for(var i = 0;i<4;i++){
		res += getBinary()
	}
	res = parseInt(res,2)
	return res>11?get11_by_binary():res
}
复制代码

当然,性能会差很多,因为太多遍历了。通用版本也不难,可以自己封装一个。

3. 总结

其实第一种方法叫做拒绝采样。我们知道等概率生成某个范围的随机数,想通过这个函数生成一个更小范围的随机数,就应该这样子:超过预期范围,重新抽取,所以叫做拒绝采样。 基本的操作:

//我们还是用get7获取1到小于7的随机数
function getn(n){//n是小于7的正整数
    var num = get7()
    return num > n?getn(n):num
}

//while形式
function getn(n){
	var t
	do{
		t = get7()
	}while(t>n)
	return t
}
复制代码

那我们get14就可以很灵活获得了,7*2得到14是吧,那就来:

function get14(){
	var t
	do{
		t = get7()
	}while(t>2)//我们就叫他get2吧
	return get7() + 7 * (t -1) //上面的a*(getx - 1) + getx公式的变种,这个a等于7
}
复制代码

都get14了,那get11还会远吗,大于11就拒绝采样咯。前面说先要get49?这只是一个循序渐进的过程,这样子你可以深刻理解到这个过程要怎么来,是不是感觉拒绝采样很灵活?

公式推广: 已知生成器getn能生成1-n的随机数,那么由getn拒绝采样得到的新生成器geta和getb(a,b都不大于n),可以生成get(a*b):

get(a*b) = geta + a*(getb-1)//公式是对称的,可以交换a和b


//上面的例子用公式解释
get14() = get7() + 7 * (get2() -1) = get2() + 2*(get7() -1)
//其实get10也可以
get10() = get5() + 5 * (get2() -1) = get2() + 2*(get5() -1)
复制代码

get7能获得get2,那get14就可以得到了还可以获得get5,那get10也是可以做到。刚刚好就是最完美的,如果目标生成器是质数,就让拒绝采样次数尽量少,也就是尽量靠近目标。这种随机数扩展, 套路就是超过的拒绝采样,不足的利用加法和乘法使得刚刚好到目标范围或者超过目标

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

TensorFlow极简入门教程

随着 TensorFlow 在研究及产品中的应用日益广泛,很多开发者及研究者都希望能深入学习这一深度学习框架。本文介绍了TensorFlow 基础,包括静态计算...

1594
来自专栏应兆康的专栏

Aggomerative Clustering

所有观测对象先以自己为群组,满足特定准则的对象汇聚在一起。重复这个过程,群组不断增大,直到某个端点饱和。

890
来自专栏简书专栏

基于tensorflow+RNN的MNIST数据集手写数字分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 RNN是recurrent neural network的简...

1743
来自专栏IT派

【深度学习入门系列】TensorFlow训练线性回归

作者:董超 来源:腾讯云技术社区「腾云阁」 上一篇文章我们介绍了 MxNet 的安装,但 MxNet 有个缺点,那就是文档不太全,用起来可能是要看源代码才能理...

3323
来自专栏MelonTeam专栏

深度学习入门实战(二)

导语:上一篇文章我们介绍了MxNet的安装,但MxNet有个缺点,那就是文档不太全,用起来可能是要看源代码才能理解某个方法的含义,所以今天我们就介绍一下Te...

24410
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之哈夫曼编码

第二步,将两个最小概率组成一组,划成2 个分支域,并标以0 和1;再把2 个分支域合并成1个支域,标以两个概率之和;

1192
来自专栏深度学习自然语言处理

PyTorch(总)---PyTorch遇到令人迷人的BUG与记录

BUG1 在使用NLLLoss()激活函数时,NLLLoss用来做n类分类的,一般最后一层网络为LogSoftmax,如果其他的则需要使用CrossEntrop...

9088
来自专栏深度学习入门与实践

【深度学习系列】PaddlePaddle之数据预处理

  上篇文章讲了卷积神经网络的基本知识,本来这篇文章准备继续深入讲CNN的相关知识和手写CNN,但是有很多同学跟我发邮件或私信问我关于PaddlePaddle如...

2588
来自专栏java初学

MD5算法

2996
来自专栏简书专栏

基于tensorflow的MNIST数据集手写数字分类预测

MNIST是Mixed National Institue of Standards and Technology database的简称,中文叫做美国国家标准...

1933

扫码关注云+社区

领取腾讯云代金券