背景

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