背景

多选的应用场景。

比如在 菜品-材料-供应商 的角色中。会有这样两样的需求

  1. 在有材料 X（{x1, x2 ...}）的情况下，可以做出哪些菜品（A1, A2, A3...分别需要 {a11, a12...}, {a21, a22...}, {a31, a32}... 的原材料）
  2. 在需要材料 X（{x1, x2 ...}）的情况下，选择哪家供应商可以一次性采购完全（B1, B2, B3...）

对于问题 1，即找到 $A_i \sub X$ 的全部的 $A_i$

对于问题 2，即找到 $X \sub B_i$ 的全部 $B_i$

计算

这些数据是放到 MySQL 中的，可选项（食材）不是很多，暂定比如 20 样。但是菜品的可选项以及供应商的可选项很多（$2^{20} = 1048576$），开始时，采用的是 JSON 字段类型，通过 JSON_CONTAINS 进行判断。

但是这个在需求 2 勉强可以满足（对于 $x_i$ 依次进行筛选，选完包含 $x_1$ 的，然后继续筛选包含 $x_2$ 的，等等这样依次进行下去，直到全部选择完成。）

而对于需求 1 似乎无解（对于食材需要 $a$ 但是当前储备没有 $a$ 的情况的时候，很难进行判断）

后来偶然考虑到了位运算

位运算

先看一样食材 a

分别用 0、1 表示需要/储备/满足需求、不需要/未储备/不满足需求 两个情况。A 表示食材需求，B 表示供应商，X 表示储货。

AX是否可用----------XB是否可用
001 001
011 011
100 100
111 111

可以发现，A-X，X-B 的情况是一样的。这时计算 OR、AND 备用

AXorand是否可用----------XBorand是否可用
00001 00001
01101 01101
10100 10100
11111 11111

可以注意到，在可用的情况下，满足 A or X = X，X and B = X （或者说，A and X = A，X or B = B）

上面是只有一种材料的情况下。而当位数扩展后，从逻辑运算扩展到位运算，依然满足这个性质。

  1. 在有材料 X（{x1, x2 ...}）的情况下，可以做出哪些菜品（A1, A2, A3...分别需要 {a11, a12...}, {a21, a22...}, {a31, a32}... 的原材料）
    A or X = X, A and X = A
  2. 在需要材料 X（{x1, x2 ...}）的情况下，选择哪家供应商可以一次性采购完全（B1, B2, B3...）
    B and X = X, B or X = B

因此可以考虑 MySQL 实现。（为了方便显示，使用了 bit 类型，实际上可以用 int 等类型）

drop table if exists `food`;
drop table if exists `supply`;
create table `food`(
    ​`need` bit(3)
); 

insert into `food` (`need`) values
(B'000'), (B'001'), (B'010'), (B'011'), (B'100'), (B'101'), (B'110'), (B'111');

create table `supply` (
    `goods` bit(3)
);

insert into `supply` (`goods`) values
(B'000'), (B'001'), (B'010'), (B'011'), (B'100'), (B'101'), (B'110'), (B'111');

-- 假设储货为 110，可以做到的食物为 000, 010, 100, 110
select * from `food` where `need` | (B'110') = (B'110');

-- 假设需求为 110，则可以满足的供应商为 110, 111
select * from `supply` where `goods` & (B'110') = (B'110');
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏