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

Question

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

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

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

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

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

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

Мой 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 в группу доступности базы данных:

1. найти все "корневые подмножества" rs_i для v в DAG, т. е. подмножества v, так что ни один из подмножеств rs_i не является подмножеством 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)
    }

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

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

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

Answer 2

Предположим, ваш DAG G содержит узел v для каждого набора с атрибутами v.s (набор) и v.count (количество экземпляров набора), включая узел 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))))

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