Блог

Предыстория. У меня есть числа от 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} первый или второй набор.

Это решение с 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(' '))