基于动态筛选器的数组子数组提取算法实现问询

问题背景 #

我正在开发聊天机器人的表单模块，需要实现系统根据JSON属性自动匹配提交表单的endpoint（数据均持久化在数据库中并存在关联关系）。作为个人技术挑战，我希望开发一套算法来完成以下核心逻辑：

输入输出定义 #

输入1：动态筛选器（Group A）
["name", "name", "name", "email", "breed", "age", "age", "school"]

输入2：候选Endpoint集合（Group B）
[["name", "age", "email"], ["name", "breed", "age"], ["name", "age"], ["name", "age", "school"], ["name", "email"]]

期望输出
[["name", "email"], ["name", "age", "school"], ["name", "breed", "age"]]

核心规则 #

• 每匹配一个候选Endpoint的属性数组，需从动态筛选器中移除对应数量的相同元素，筛选器实时更新
• 错误的匹配顺序会导致筛选器无法清空，算法需支持回溯，尝试不同组合路径
• 最终结果仅两种情况：找到能完全清空筛选器的匹配组合，或所有组合均无法清空则返回null
• 场景中不存在两个Endpoint属性完全相同的情况，无需处理此类冲突

补充示例说明 #

动态筛选器：[1, 1, 2, 3, 3]
候选数组：[[1, 2, 3], [1, 2], [1, 3]]

若先选[1,2]，筛选器变为[1,3,3]，后续无法清空；但先选[1,2,3]，筛选器变为[1,3]，再选[1,3]即可清空，此时有效结果为[[1,2,3], [1,3]]。

算法实现思路 #

1. 计数映射优化：将筛选器和候选数组转换为元素-计数的Map结构，避免频繁操作数组的性能开销
2. 回溯递归逻辑：
   • 遍历所有候选Endpoint，检查当前筛选器是否满足该候选的元素数量需求
   • 若满足，复制筛选器计数并减去候选对应元素的数量，递归处理剩余筛选器
   • 递归终止条件：筛选器所有元素计数清零，返回当前匹配路径
   • 路径走不通时回溯，恢复计数状态并尝试下一个候选
3. 提前终止剪枝：找到有效结果后立即终止递归，避免不必要的计算

TypeScript代码实现 #

// 将数组转换为元素-计数的映射
const createCountMap = <T>(arr: T[]): Map<T, number> => {
  const map = new Map<T, number>();
  for (const item of arr) {
    map.set(item, (map.get(item) || 0) + 1);
  }
  return map;
};

// 检查候选数组是否能被当前筛选器支持（元素数量足够）
const canMatch = <T>(candidate: T[], filterMap: Map<T, number>): boolean => {
  const candidateMap = createCountMap(candidate);
  for (const [item, count] of candidateMap) {
    if ((filterMap.get(item) || 0) < count) {
      return false;
    }
  }
  return true;
};

// 复制筛选器映射并减去候选的元素计数
const subtractCandidate = <T>(filterMap: Map<T, number>, candidate: T[]): Map<T, number> => {
  const newMap = new Map(filterMap);
  const candidateMap = createCountMap(candidate);
  for (const [item, count] of candidateMap) {
    const updatedCount = newMap.get(item)! - count;
    updatedCount > 0 ? newMap.set(item, updatedCount) : newMap.delete(item);
  }
  return newMap;
};

// 回溯算法核心：寻找能清空筛选器的匹配组合
const findMatchingEndpoints = <T>(filter: T[], candidates: T[][]): T[][] | null => {
  let result: T[][] | null = null;

  const backtrack = (currentFilterMap: Map<T, number>, path: T[][]) => {
    // 筛选器已清空，找到有效路径
    if (currentFilterMap.size === 0) {
      result = [...path];
      return true;
    }

    for (const candidate of candidates) {
      if (result) return true; // 找到结果后提前终止
      if (!canMatch(candidate, currentFilterMap)) continue;

      const newFilterMap = subtractCandidate(currentFilterMap, candidate);
      path.push(candidate);
      if (backtrack(newFilterMap, path)) return true;
      path.pop(); // 回溯
    }
    return false;
  };

  backtrack(createCountMap(filter), []);
  return result;
};

// 测试主示例
const filter = ["name", "name", "name", "email", "breed", "age", "age", "school"];
const candidates = [["name", "age", "email"], ["name", "breed", "age"], ["name", "age"], ["name", "age", "school"], ["name", "email"]];
console.log(findMatchingEndpoints(filter, candidates));
// 输出：[ [ 'name', 'email' ], [ 'name', 'age', 'school' ], [ 'name', 'breed', 'age' ] ]

// 测试补充示例
const filter2 = [1, 1, 2, 3, 3];
const candidates2 = [[1, 2, 3], [1, 2], [1, 3]];
console.log(findMatchingEndpoints(filter2, candidates2));
// 输出：[ [ 1, 2, 3 ], [ 1, 3 ] ]

内容的提问来源于stack exchange，提问作者I'ma Chris