Генерировать DAG из поса

Question

Вот моя проблема: у меня есть последовательность S (непустых, но, возможно, не отдельных) наборов S_i, и для каждого S_i нужно знать, сколько наборов S_J в s (i ≠ j) являются подмножествами s_i.

Мне также нужна инкрементная производительность: как только у меня есть все свои подсчеты, я могу заменить один набор S_i на некоторую подмножество S_I и обновить счетчик постепенно.

Выполнение всего этого с использованием чисто функционального кода было бы огромным плюсом (I код в Scala).

Поскольку установленное включение является частичным упорядочением, я подумал, что лучший способ решить мою проблему - создать DAG, который будет представлять диаграмму Hasse наборов, с ребрами, представляющими включение, и присоединиться к целочисленному значению к каждому узлу, представляющему размер Подпрограмма ниже узла плюс 1. Однако я застрял в течение нескольких дней, пытаясь разработать алгоритм, который создает диаграмму Hasse из частичного упорядочения (давайте не будем говорить о инкрементности!), Даже если я думал, что это будет некоторая часть Стандартный бакалавриат.

Вот моя структура данных:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

Мой даг определяется списком корней и некоторым частичным упорядочением:

class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
  def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))

  private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (roots == Nil) collected
    else {
      val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
      collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
    }
}

Я здесь довольно застрял. Последнее, что я пришел, чтобы добавить новое значение V в DAG, это:

1. Найдите все «корневые подмножества» rs_i of v в DAG, т. Е. Подмножества V, так что ни один из них не является подмножеством v. Это можно легко сделать, выполнив поиск (BFS или DFS) на графике (collect функция, возможно, не оптимальная или даже ошибочная).
2. Создайте новый узел N_V, дети которых являются ранее найденными RS_I.
3. Теперь давайте выясним, где N_V должен быть прикреплен: для данного списка корней, узнайте суперсеты V. Если никто не найден, добавьте N_V в корни и удалите подмножества n_v из корней. Иначе выполните шаг 3 рекурсивно на детях Суперсет.

Я еще не внедрил этот алгоритм, но он кажется бессмысленно -циркулированным и не оптимальным для моей явно простой проблемы. Есть ли доступен какой -то более простой алгоритм (Google был невежественным по этому поводу)?

Answer 1

После некоторой работы я наконец -то закончил решить свою проблему после моей первоначальной интуиции. Метод сбора и оценка ранга были ошибочными, я переписал их с помощью хвостовой рекурсии в качестве бонуса. Вот код, который я получил:

final case class HNode[A](
  val v: A,
  val child: List[HNode[A]]) {
  val rank: Int = 1 + count(child, Set.empty)

  @tailrec
  private def count(stack: List[HNode[A]], c: Set[HNode[A]]): Int =
    if (stack == Nil) c.size
    else {
      val head :: rem = stack
      if (c(head)) count(rem, c)
      else count(head.child ::: rem, c + head)
    }
}

// ...

  private def add(v: A, roots: List[HNode[A]]): List[HNode[A]] = {
    val newNode = HNode(v, collect(v, roots, Nil))
    attach(newNode, roots)
  }

  private def attach(n: HNode[A], roots: List[HNode[A]]): List[HNode[A]] =
    if (roots.contains(n)) roots
    else {
      val (supersets, remaining) = roots.partition { r =>
        // Strict superset to avoid creating cycles in case of equal elements
        po.tryCompare(n.v, r.v) == Some(-1)
      }
      if (supersets.isEmpty) n :: remaining.filter(r => !po.lteq(r.v, n.v))
      else {
        supersets.map(s => HNode(s.v, attach(n, s.child))) ::: remaining
      }
    }

  @tailrec
  private def collect(v: A, stack: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
    if (stack == Nil) collected
    else {
      val head :: tail = stack

      if (collected.exists(c => po.lteq(head.v, c.v))) collect(v, tail, collected)
      else if (po.lteq(head.v, v)) collect(v, tail, head :: (collected.filter(c => !po.lteq(c.v, head.v))))
      else collect(v, head.child ::: tail, collected)
    }

Теперь я должен проверить некоторую оптимизацию: - Отключить ветви с совершенно отдельными наборами при сборе подмножеств (как предложил Рекс Керр) - Посмотрите, улучшает ли сортировка наборов по размеру процесс (как предложил Митчус)

Следующая проблема состоит в том, чтобы выпустить (худший) сложность операции add (). С n количество наборов, и D размером с самый большой набор, сложность, вероятно, будет O (N²D), но я надеюсь, что она может быть уточнена. Вот мои рассуждения: если все наборы различны, DAG будет уменьшен до последовательности корней/листьев. Таким образом, каждый раз, когда я пытаюсь добавить узел в структуру данных, мне все равно приходится проверить включение с каждым уже присутствующим узлом (как в процедурах сбора, так и прикрепления). Это приводит к 1 + 2 +… + n = n (n + 1)/2 ∈ O (N²) проверки включения.

Каждый набор теста включения o (d), отсюда и результат.

Answer 2

Предположим, ваш даг G содержит узел v Для каждого набора, с атрибутами v.s (набор) и v.count (Количество экземпляров набора), включая узел G.root с G.root.s = union of all sets (куда G.root.count=0 Если этот набор никогда не происходит в вашей коллекции).

Затем подсчитать количество отдельных подмножеств s Вы могли бы сделать следующее (в ублюдке смеси Scala, Python и Pseudo-Code):

sum(apply(lambda x: x.count, get_subsets(s, G.root)))

куда

get_subsets(s, v) :
   if(v.s is not a subset of s, {}, 
      union({v} :: apply(v.children, lambda x: get_subsets(s, x))))

По моему мнению, по причинам производительности вам было бы лучше отказаться от такого рода чисто функционального решения ... оно хорошо работает на списках и деревьях, но помимо этого становится тяжелым.