给定多个集合，如何找到每个集合中对所有其他子集唯一的最小子集？

Question

背景。我有数字 1 到 20（黑色背景上的白色数字）可以出现在屏幕上，我希望识别这些数字。由于无法简单地复制粘贴它们，因此我将把屏幕上数字的白色像素位置与所有 20 个数字的白色像素位置列表进行比较。然而，每个数字可以具有大量像素，并且可能不需要比较所有这些像素来识别该数字。因此，我希望进行尽可能少的比较。

算法问题：我有多个集合，每个集合中的元素都是唯一的，但在所有集合中可能不是唯一的。如何找到每个集合的最小可能子集，使得每个子集都是唯一的？

示例 1： 设 A = {1, 2}，B = {3, 4}。 A 和 B 的最小子集将是 {1} 和 {3}（或 {2} 和 {4}），因为这些子集对于每个原始集合都是唯一的，并且尽可能小。

例2：设A = {1, 2, 3, 4}，B = {1, 2, 3, 5}，C = {1, 2, 4, 5}。可能的最小子集是{3, 4}、{3, 5}、{4, 5}。如果从任何这些子集中删除了任何元素，则该子集也可以属于不同的集合。例如。从第一个子集中删除 4 将留下 {3}，这使得 {3} 标识第一组还是第二组变得不明确。

Answer 1

这是一个时间复杂度为 O(n^3)、内存复杂度为 O(n) 的解决方案。 （如果我没记错的话）

function isElement(elem, s) {
  return s.includes(elem)
}

function isId(id, sets) {
  let setsWithSuchElementsNumber = 0
  for (const s of sets) {
    if (id.every((e) => isElement(e, s))) {
      setsWithSuchElementsNumber++
    }
  }

  return setsWithSuchElementsNumber === 1
}

function getSetId(s, sets) {
  const count = {}
  const elements = []
  for (const elem of s) {
    if (count[elem] == null) {
      elements.push(elem)
    }
    count[elem] = 0
  }

  for (const otherSet of sets) {
    for (const e of elements) {
      if (isElement(e, otherSet)) {
        count[e]++
      }
    }
  }

  elements.sort((first, second) => {
    return Math.sign(count[first] - count[second])
  })

  for (let idSize = 1; idSize <= elements.length; idSize++) {
    const possibleId = elements.slice(0, idSize)

    if (isId(possibleId, sets)) {
      return possibleId
    }
  }

  return null
}

const getSetIds = (sets) => {
  return sets.map((s) => getSetId(s, sets))
}

const res = getSetIds([
  [1, 2, 3, 4],
  [1, 2, 3, 5],
  [1, 2, 4, 5],
])

console.log(res.join(' '))

Answer 2

我最近写了一个Python包，旨在有效地解决你的算法问题：https://github.com/alussana/TrieSUS

我偶然发现了一个类似的问题，我很惊讶没有找到这个算法问题的名称。我只能找到涉及枚举和比较幂集以找到每个集合的解决方案的蛮力方法 - 这是非常低效的，并且在考虑不存在解决方案的集合时尤其慢。

我的算法使用 trie 数据结构和一系列线性时间操作，首先大大减小问题规模，然后将其转化为相当于 集合覆盖问题，其解是使用 OR 提取的-Tools 的约束编程求解器。有关算法及其性能的更多信息可以在存储库中找到。