Создание DAG из poset с использованием строго функционального программирования

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

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

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

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

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

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

My DAG определяется списком корней и некоторым частичным порядком:

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:

  • найти все "корневые подмножества" rs_i из v в DAG, т.е. подмножества v, такие, что никакое надмножество rs_i не является подмножеством v. Это можно сделать довольно легко, выполнив поиск (BFS или DFS) на graph (collect функция, возможно, неоптимальная или даже некорректная).
  • создайте новый node n_v, дочерние элементы которого ранее были найдены rs_i.
  • Теперь давайте узнаем, где нужно присоединить n_v: для данного списка корней найдите супермножества v. Если ни один не найден, добавьте n_v к корням и удалите подмножества n_v из корней. Else, выполните шаг 3 рекурсивно над дочерними элементами надстроек.

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

Ответы

Ответ 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 будет сведена к последовательности корней/листьев. Таким образом, каждый раз, когда я пытаюсь добавить структуру node в структуру данных, мне все равно нужно проверить включение с каждым node уже присутствующим (как в процедурах сбора, так и при вставке). Это приводит к проверке включения 1 + 2 +... + n = n (n + 1)/2 ∈ O (n²).

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

Ответ 2

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

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

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

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