V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
songz
V2EX  ›  Node.js

关于盲盒概率的计算问题

  •  
  •   songz · 2021-01-11 14:42:11 +08:00 · 3589 次点击
    这是一个创建于 1397 天前的主题,其中的信息可能已经有所发展或是发生改变。

    背景

    • 假设有 M 个盒子里装着 N 个不同类型的玩具
    • 假设 N=M
    • 每个盒子都会提示某 3 个玩具不可能出现在里面

    问题

    • 当样本 MN=12 时报错
    var artObjects = ["dbld", "db", "fdm", "hg", "hm", "le", "mef", "mg", "hlbt", "lp", "xtlx", "lw"]
    
    var impossibleObjects = [
        ["fdm", "lw", "mef"],//第 1 个格子不会出现的物品
        ["fdm", "xtlx", "hm"],//第 2 个格子不会出现的物品
        ["dbld", "fdm", "hlbt"],//第 3 个格子不会出现的物品
        ["fdm", "db", "hg"],//...
        ["hlbt", "lp", "db"],//...
        ["lw", "lp", "mef"],
        ["xtlx", "db", "fdm"],
        ["mef", "hg", "hlbt"],
        ["hg", "le", "xtlx"],
        ["le", "lw", "lp"],
        ["mg", "hm", "mef"],
        ["lw", "mg", "le"]
    ]
    

    报错

    <--- Last few GCs --->
    
    [2338:0x108008000]    30104 ms: Scavenge 4052.4 (4129.0) -> 4047.7 (4130.5) MB, 4.0 / 0.0 ms  (average mu = 0.210, current mu = 0.145) allocation failure 
    [2338:0x108008000]    30111 ms: Scavenge 4054.0 (4130.5) -> 4049.1 (4131.8) MB, 3.7 / 0.0 ms  (average mu = 0.210, current mu = 0.145) allocation failure 
    [2338:0x108008000]    30653 ms: Scavenge 4055.4 (4131.8) -> 4050.6 (4147.8) MB, 538.3 / 0.0 ms  (average mu = 0.210, current mu = 0.145) allocation failure 
    
    
    <--- JS stacktrace --->
    
    FATAL ERROR: MarkCompactCollector: young object promotion failed Allocation failed - JavaScript heap out of memory
    
    • 当样本 M=N=6 时没有问题
    var artObjects = ["女孩", "男孩", "乳牛", "博客", "甜点", "朋克"]
    
    var impossibleObjects = [
        ["甜点", "朋克", "女孩"],
        ["乳牛", "甜点", "博客"],
        ["女孩", "乳牛", "甜点"],
        ["甜点", "乳牛", "男孩"],
        ["博客", "女孩", "男孩"],
        ["朋克", "男孩", "博客"]
    ]
    

    结果

    女孩:[0,41,0,41,0,17]
    男孩:[35,29,35,0,0,0]
    乳牛:[29,0,0,0,35,35]
    博客:[35,0,35,29,0,0]
    甜点:[0,0,0,0,52,47]
    朋克:[0,29,29,29,11,0]
    

    请教

    在 node 环境下如何让脚本在样本等于 MN=12 时正常输出?

    js 脚本

    数组全排列用的这里 https://github.com/GDUFXRT/NOTES/tree/master/permutation

    function permutation(a, m) {
    
        let result = [];
        let n = a.length;
        m = m || n;
    
        function recur(_a, tmpResult = []) {
            if (tmpResult.length === m) {
    
                result.push(tmpResult);
    
            } else {
                for (let i = 0; i < _a.length; i++) {
    
                    let tmpA = _a.concat();
    
                    let _tmpResult = tmpResult.concat();
    
                    _tmpResult.push(tmpA[i]);
    
                    tmpA.splice(i, 1);
                    recur(tmpA, _tmpResult);
                }
            }
        }
    
        recur(a);
        return result;
    }
    
    
    //12 个物品放在 12 个格子
    var artObjects = ["dbld", "db", "fdm", "hg", "hm", "le", "mef", "mg", "hlbt", "lp", "xtlx", "lw"]
    
    var impossibleObjects = [
        ["fdm", "lw", "mef"],//第 1 个格子不会出现的物品
        ["fdm", "xtlx", "hm"],//第 2 个格子不会出现的物品
        ["dbld", "fdm", "hlbt"],//第 3 个格子不会出现的物品
        ["fdm", "db", "hg"],//...
        ["hlbt", "lp", "db"],//...
        ["lw", "lp", "mef"],
        ["xtlx", "db", "fdm"],
        ["mef", "hg", "hlbt"],
        ["hg", "le", "xtlx"],
        ["le", "lw", "lp"],
        ["mg", "hm", "mef"],
        ["lw", "mg", "le"]
    ]
    
    var allArray = permutation(artObjects)
    
    var arrayGroup = [allArray]
    
    for (var i = 0; i < artObjects.length; i++) {
    
        arrayGroup[i + 1] = []
    
        for (var j = 0; j < arrayGroup[i].length; j++) {
    
            if ((arrayGroup[i][j][i] !== impossibleObjects[i][0]) &&
                (arrayGroup[i][j][i] !== impossibleObjects[i][1]) &&
                (arrayGroup[i][j][i] !== impossibleObjects[i][2]) &&
                (arrayGroup[i][j][i] !== (impossibleObjects[i][3] !== undefined ? impossibleObjects[i][3] : ""))) {
    
                arrayGroup[i + 1].push(arrayGroup[i][j])
            }
        }
    
        console.log(arrayGroup[i + 1].length)
    
    }
    var finalArray = arrayGroup[arrayGroup.length - 1]
    
    var resultGroup = {}
    
    for (var i = 0; i < artObjects.length; i++) {
    
        resultGroup[artObjects[i]] = []
    
        for (var a = 0; a < artObjects.length; a++) {
    
            resultGroup[artObjects[i]][a] = []
        }
    
        for (var f = 0; f < finalArray.length; f++) {
    
            for (var t = 0; t < artObjects.length; t++) {
    
                if (finalArray[f][t] == artObjects[i]) {
    
                    resultGroup[artObjects[i]][t].push(finalArray[f])
                }
            }
    
        }
        console.log(artObjects[i] + ":" + JSON.stringify(resultGroup[artObjects[i]].map((count) => Math.floor(count.length / finalArray.length * 100))))
    
    }
    
    11 条回复    2021-01-12 14:34:41 +08:00
    misdake
        1
    misdake  
       2021-01-11 14:53:40 +08:00
    上来就求全排列,12!=479001600 种情况,每一个都是 12 长度的字符串数组,每几十上百 GB 内存是不够的
    shintendo
        2
    shintendo  
       2021-01-11 14:56:06 +08:00
    虽然你的提问很详细,排版干净令人赏心悦目,但既然是程序崩溃而不是结果错误,其实只要贴出代码然后问为什么崩溃就好,我还读了半天背景问题……话说你这个明显是递归过深爆栈了吧
    banricho
        3
    banricho  
       2021-01-11 15:00:30 +08:00
    能把求助贴发成这样也是套路很深
    misdake
        4
    misdake  
       2021-01-11 15:06:43 +08:00   ❤️ 1
    如果能每次求出一个排列就进行统计的话,内存就应该够了。而不是把指数级的的可能结果全部放到一个数组里再一个一个统计。
    另外推荐仔细学习一下全排列的代码,把你这个 impossibleObjects 的逻辑放到全排列里进行剪枝,性能会好很多。
    songz
        5
    songz  
    OP
       2021-01-11 15:10:59 +08:00
    @misdake 谢谢你的思路!
    shintendo
        6
    shintendo  
       2021-01-11 16:18:15 +08:00   ❤️ 1
    alan0liang
        7
    alan0liang  
       2021-01-11 16:27:35 +08:00 via Android   ❤️ 1
    @shintendo 不是爆栈了,爆栈了是这样的:RangeError: Maximum call stack size exceeded

    如果只是想强行调大 node 内存上限的话可以用 node --max-old-space-size=4096 file.js 。
    songz
        8
    songz  
    OP
       2021-01-11 18:01:52 +08:00
    @shintendo #6 感谢!代码优雅多了,也不报错!
    dangyuluo
        9
    dangyuluo  
       2021-01-11 18:07:33 +08:00
    不是 stack,是 heap 爆了
    krixaar
        10
    krixaar  
       2021-01-12 11:15:14 +08:00   ❤️ 2
    这个问题看起来简单实际上很炸裂啊……
    这就是个 Constrained N-rooks problem,可以抽象成二分图( Bipartite graph ),求排列的个数等同于求二分图完美匹配( Perfect matching )的个数,等同于把矩阵列成 0 和 1,0 代表不可放置,1 代表可放置,然后求这个矩阵的积和式( Permanent )……
    求积和式除了暴力之外,还有 Ryser formula,从 StackExchange 抄了个实现代码粗略改了下( Python,因为我懒):
    https://gist.github.com/Raka-loah/d11e340998d76829e7b8f81a36846683

    12x12 的情况似乎就非常趋近于概率均匀分布了。
    no1xsyzy
        11
    no1xsyzy  
       2021-01-12 14:34:41 +08:00
    能不能用 DP (不是分阶段 DP )
    每次固定 M-1 个盒子的概率求解某一盒中的概率,直觉上是收敛的或者震荡的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2548 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 01:33 · PVG 09:33 · LAX 17:33 · JFK 20:33
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.