关于盲盒概率的计算

前言

一组盲盒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 国际许可协议进行许可。转载请注明出处！