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也是可以做到。刚刚好就是最完美的，如果目标生成器是质数，就让拒绝采样次数尽量少，也就是尽量靠近目标。这种随机数扩展，套路就是超过的拒绝采样，不足的利用加法和乘法使得刚刚好到目标范围或者超过目标

js随机数生成器的扩展