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

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(' '))