BigQuery实现6列数据下4种唯一物品不放回抽取次数计算

核心逻辑 #

首先明确判定规则：每次抽取需要凑齐4类不同物品，记每行6类物品（keys、skulls、gems、coins、daggers、crowns）的持有数量为v₁~v₆，总物品数为S，最多可完成的抽取次数t是满足以下条件的最大非负整数：

• 所有类别的min(vᵢ, t)之和 ≥ 4*t
  （逻辑说明：t次抽取中，每个类别最多被抽到t次，同时不可能超过自身持有量，所有被抽取的物品总数需要达到4t才能凑齐t次、每次4个不同类的要求）
• t的理论上限为S//4（总物品数除以4向下取整），因为每次抽取固定消耗4个物品，总数量决定了抽取次数不可能超过该值

实现SQL #

假设原始表存储路径为项目名.数据集名.表名，包含current_holder、keys、skulls、gems、coins、daggers、crowns字段，计算代码如下：

WITH item_data AS (
  SELECT
    *,
    -- 将6类物品数量组装为数组简化后续计算
    [keys, skulls, gems, coins, daggers, crowns] AS item_counts,
    -- 计算单用户总物品数
    keys + skulls + gems + coins + daggers + crowns AS total_items
  FROM `你的项目名.你的数据集名.你的表名`
)
SELECT
  * EXCEPT(item_counts, total_items, t),
  MAX(t) AS max_draw_times
FROM item_data,
-- 生成所有可能的t候选值，范围从0到总物品数//4
UNNEST(GENERATE_ARRAY(0, DIV(total_items, 4))) AS t
WHERE
  -- 筛选符合抽取条件的t值
  (SELECT SUM(LEAST(cnt, t)) FROM UNNEST(item_counts) AS cnt) >= 4 * t
GROUP BY current_holder, keys, skulls, gems, coins, daggers, crowns

结果验证 #

对应给出的3个示例场景，计算结果完全匹配预期：

• 示例1：物品数量为[0,0,6,7,8,9]（skulls持有量为6，两类物品持有量为0），总物品数30，t上限为7。t=7时sum(least(vᵢ,7))=27 < 28不满足要求，最大符合条件的t为6
• 示例2：非零物品类数小于4，t=1时sum(least(vᵢ,1)) <4不满足要求，结果为0
• 示例3：物品数量为[0,4,4,5,5,5]（skulls持有量为4），总物品数23，t上限为5，t=5时sum(least(vᵢ,5))=23 >=20满足要求，结果为5

如果单条记录的物品总量极大（单用户总物品超过10万级别），可以改用二分法查找t值避免生成过长数组，绝大多数业务场景下上述写法性能足够。

内容的提问来源于stack exchange，提问作者locket