[mc命令]一种可靠的生成不重复随机数的方法
小豆8593
2022年06月07日 14:29

    何为生成不重复随机数的方法?问题的情景是这样的:我们假定随机范围最小值是0,输入n int和max int两个分数(这里保证n<=max),要在[0,max)区间内取n个随机数,且它们各不相同。

    何为"可靠&#​34;?"可靠&#​34;是相对于不可靠的方法来说的。

    第一种不可靠的方法,是生成max个实体,它们的分数从0到max-1分布,利用选择器参数sort=random来选取n个作为结果。当max的值过大时,这种方法由于要生成大量实体,性能开销不可接受。

    第二种不可靠的方法,是循环调用现有的生成单个随机数的random函数,每次生成的随机数用一个实体来记录,如果之前已有这个分数的实体(发生了碰撞),就销毁,继续生成,直到实体数满n为止。如果我们认为random函数理想,分析一下碰撞的概率,很容易发现这种方法的漏洞所在:当max=100,n=100时,第1个随机数碰撞的概率是0%,第2个随机数碰撞的概率是1%,第3个随机数碰撞的概率是2%......第100个随机数碰撞的概率达到了惊人的99%!那么我们就很难预计它会在何时运行结束,因此不可靠。

    我用一个简单的例子来说明我的做法:max=10

我们写出所有可以取的数的数列,此时下标上界smax=10

0,1,2,3,4,5,6,7,8,9

现在我们要生成第一个随机下标,假如生成了2,下标2对应位置的随机数是2,那么第一个随机数就生成了2。此时我们把2标红,下标上界扣1。

smax=9

0,1,2,3,4,5,6,7,8,9

意思是,2是需要被我们掠过的数字,现在只有9个随机数供我们选择。当我们再一次生成随机下标,假如生成了3,我们就需要选择第3个可供选择的随机数。从0开始向右走,遇到了2,因为2已经被标红,所以向右走的步数增加1

smax=8

0,1,2,3,4,5,6,7,8,9

......以此类推

我们发现,下标在从左向右走的过程中,每次遇到标红的数字,向右步数都会增加1。那么最终我们得到的随机数应该是:随机下标+若干个1。每个已生成的随机数会对比自己大的下标进行增加1的操作。

以下为命令的实现(单个随机数的生成方法使用了线性同余):

代码块
JavaScript
自动换行
复制代码
#math:n_rand
tag @e remove result
scoreboard players operation sloop int = n int
scoreboard players operation smax int = max int
execute if score sloop int matches 1.. run function math:loop73
复制成功

代码块
JavaScript
自动换行
复制代码
#math:loop73
summon marker 0 11 0 {Tags:["stmp"]}
execute as @e[tag=stmp,limit=1] run function math:loop73-1

scoreboard players remove smax int 1
scoreboard players remove sloop int 1
execute if score sloop int matches 1.. run function math:loop73
复制成功

代码块
JavaScript
自动换行
复制代码
#math:loop73-1
scoreboard players operation random_seed int *= 1103515245 int
execute store result score random int run scoreboard players add random_seed int 12345
scoreboard players operation random int %= smax int
execute positioned 0 -1 0 as @e[tag=result,sort=nearest] run function math:loop73-2

execute store result entity @s Pos[1] double 0.0000001 run scoreboard players operation @s int = random int
tag @s remove stmp
tag @s add result
复制成功

代码块
JavaScript
自动换行
复制代码
#math:loop73-2
execute if score @s int <= random int run scoreboard players add random int 1
复制成功

另外,值得注意的是,这里的loop73-2函数里只有一条命令。这么做是有原因的,这涉及到execute的运行原理,篇幅有限不能介绍,有疑惑的读者请自行探究。