关于盲盒概率的计算问题

[songz]

背景

• 假设有 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))))

}

[misdake]

上来就求全排列，12!=479001600 种情况，每一个都是 12 长度的字符串数组，每几十上百 GB 内存是不够的

[shintendo]

虽然你的提问很详细，排版干净令人赏心悦目，但既然是程序崩溃而不是结果错误，其实只要贴出代码然后问为什么崩溃就好，我还读了半天背景问题……话说你这个明显是递归过深爆栈了吧

[banricho]

能把求助贴发成这样也是套路很深

[misdake]

如果能每次求出一个排列就进行统计的话，内存就应该够了。而不是把指数级的的可能结果全部放到一个数组里再一个一个统计。
另外推荐仔细学习一下全排列的代码，把你这个 impossibleObjects 的逻辑放到全排列里进行剪枝，性能会好很多。

[songz]

@misdake 谢谢你的思路！

[shintendo]

https://gist.github.com/niaodan2b/7f3dc1d13b98655b8ca1dd875abb676e

供参考

[alan0liang]

@shintendo 不是爆栈了，爆栈了是这样的：RangeError: Maximum call stack size exceeded

如果只是想强行调大 node 内存上限的话可以用 node --max-old-space-size=4096 file.js 。

[songz]

@shintendo #6 感谢！代码优雅多了，也不报错！

[dangyuluo]

不是 stack，是 heap 爆了

[krixaar]

这个问题看起来简单实际上很炸裂啊……
这就是个 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]

能不能用 DP （不是分阶段 DP ）
每次固定 M-1 个盒子的概率求解某一盒中的概率，直觉上是收敛的或者震荡的