前言
一组盲盒12个,里面的玩偶完全不重样(小概率会有一个盒子里是隐藏款玩偶,不考虑)。现在可以知道每一个盲盒里没有的3种玩偶(不重复),那么怎么求某一个玩偶在某一个盲盒里的概率?
胖虎虎你是不是很想知道?认真看完这篇文章你就知道啦!
背景
假设有 M 个盒子里装着 N 个不同类型的玩具
假设 N=M
每个盒子都会提示某 3 个玩具不可能出现在里面
全排列介绍
规律
当n = 1时, 数组arr = [A],全排列结果为:
[A]
当n = 2时, 数组arr = [A, B],全排列结果为:
[A, B] [B, A]
当n = 3时, 数组arr = [A, B, C],全排列结果为:
[A, B, C] [A, C, B] [B, A, C] [B, C, A] [C, A, B] [C, B, A]
到n = 3时可以看出全排列有以下规律:
1.固定第一个元素,将剩下的元素进行全排列处理;
2.将第一个元素与依次与第i(1<i<=arr.length)个元素互换,将剩下的元素进行全排列处理;
3.结束。
很适合使用递归解决。只要写一个全排列函数permutation,能固定一个下标为i的元素,剩下元素再进行全排列即可。
代码实现
// ES6
class Permutation {
constructor(arr) {
this.arr = Array.from(arr);
this.result = [];
this.len = 0;
this.run(0);
}
run(index) {
if (index == this.arr.length - 1) {
this.result.push(Array.from(this.arr));
this.len++;
return;
}
for(let i = index; i < this.arr.length; i++) {
[this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
this.run(index + 1);
[this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
}
}
}
let p = new Permutation(["A", "B", "C"]);
console.log(p.result);
// [ 'A', 'B', 'C' ],
// [ 'A', 'C', 'B' ],
// [ 'B', 'A', 'C' ],
// [ 'B', 'C', 'A' ],
// [ 'C', 'B', 'A' ],
// [ 'C', 'A', 'B' ] ]
console.log(p.len);
// 6
以上就是全排列的实现。
实际解决方法
var artObjects = ["子鼠", "丑牛", "寅虎", "卯兔", "辰龙", "巳蛇", "午马", "未羊", "申猴", "酉鸡", "戌狗", "亥猪"];
var impossibleObjects = [
["寅虎", "亥猪", "午马"], // 第 1 个盒子不会出现的玩偶
["寅虎", "戌狗", "辰龙"], // 第 2 个盒子不会出现的玩偶
["子鼠", "寅虎", "申猴"], // 第 3 个盒子不会出现的玩偶
["寅虎", "丑牛", "卯兔"], // 以此类推
["申猴", "酉鸡", "丑牛"],
["亥猪", "酉鸡", "午马"],
["戌狗", "丑牛", "寅虎"],
["午马", "卯兔", "申猴"],
["卯兔", "巳蛇", "子鼠"],
["巳蛇", "亥猪", "酉鸡"],
["未羊", "辰龙", "午马"],
["亥猪", "未羊", "巳蛇"]
]
// 全排列逻辑
function permutation(a, callback, m) {
let n = a.length;
m = m || n;
function recur(_a, tmpResult = []) {
if (tmpResult.length === m) {
callback(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);
}
let count = {};
artObjects.forEach(x => count[x] = artObjects.map(y => 0));
permutation(artObjects, (tmpResult) => {
if (impossibleObjects.every((x, i) => !x.includes(tmpResult[i]))) {
tmpResult.forEach((x, i) => {
count[x][i] += 1;
})
}
});
artObjects.forEach(name => {
const sum = count[name].reduce((a, b) => a + b, 0);
console.log(name, ':', count[name].map(num => Math.round(num * 100 / sum)));
});
总结
这个方法有可能会导致递归过深内存不足。
解决方法:每次求出一个排列就进行统计,内存就应该够了。
本文作者: Vae
本文链接: https://www.huangchuanlin.cn/index.php/archives/web-12
版权声明: 本博客所有文章除特别声明外,均采用 知识共享署名 4.0 国际许可协议进行许可。转载请注明出处!
哇塞!好棒棒呀!大垃圾
还是小野菜厉害些~