如何检测stubs与poolList组合是否存在选择耗尽失败的可能性？

问题回顾 #

我们有两个核心列表：

• poolList：每个元素是一组标签，选中后会从列表中移除
• stubs：每个元素是一组标签，只需匹配poolList中任意包含交集标签的项即可选中，选中后对应poolList项被耗尽

需要判断：是否存在一种恶意的选择策略（每次选当前stub能匹配的、但会最大化后续匹配难度的pool项），导致某个stub无法找到可匹配的pool项。

核心检测算法（基于集合论） #

无需穷举所有排列，只需通过以下步骤检测是否存在冲突：

1. 定义关键指标 #

对每个标签t，计算三个核心值：

• A：poolList中包含标签t的项的总数
• B：既能被包含t的pool项满足，又能被不包含t的pool项满足的stubs数量（这类stubs的标签集合与t有交集，同时也与其他标签有交集，可被替代匹配）
• C：只能被包含t的pool项满足的stubs数量（这类stubs的标签集合，无法与任何不包含t的pool项产生交集，没有替代匹配选项）

2. 冲突判断规则 #

如果存在任意标签t满足：

C > max(A - B, 0)

则说明存在最坏情况：我们可以先耗尽min(A, B)个带t的pool项去满足那些可替代的stubs，剩余的带t的pool项数量不足以覆盖专属stubs的需求，最终导致某个stub无法匹配。

算法验证（针对示例1） #

示例1参数：

const poolList = [[low, med], [low], [low], [low, med], [high, med]];
const stubs = [[low], [low], [med], [high]];

以标签high为例：

• A：带high的pool项仅[high, med]，数量为1
• B：可被high或其他标签满足的stubs是[med]（med可匹配带low+med或high+med的项），数量为1
• C：只能被high满足的stubs是[high]，数量为1

代入规则：max(1-1, 0) = 0，而1 > 0，满足冲突条件，因此存在最坏情况导致失败，与示例描述一致。

复杂度说明 #

该算法的时间复杂度为O(M*N + K*N)，其中：

• M = poolList的长度
• K = stubs的长度
• N = 所有标签的总数量
  完全规避了穷举排列带来的O(n!)超高复杂度。

补充说明 #

• 如果某个stub本身没有任何可匹配的pool项（无论选择顺序），算法也会检测到冲突（此时对应专属标签的A=0，C≥1，必然满足冲突条件）。
• 若没有任何标签满足冲突规则，则说明无论如何恶意选择，都能完成所有stub的匹配。

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