Generar un DAG a partir de un POSET utilizando programación estricta funcional

Question

Aquí está mi problema: tengo una secuencia S de los conjuntos (no vacíos pero posiblemente no distintos) S_I, y para cada S_i necesito saber cuántos conjuntos S_J en S (i ≠ J) son subconjuntos de S_i.

También necesito un rendimiento incremental: una vez que tengo todos mis recuentos, puedo reemplazar un conjunto S_i por algún subconjunto de S_I y actualizar los recuentos de forma incremental.

Realizar todo esto usando código puramente funcional sería una gran ventaja (código I en Scala).

Como la inclusión de set es un orden parcial, pensé que la mejor manera de resolver mi problema sería construir un DAG que represente el diagrama de Hasse de los conjuntos, con bordes que representan la inclusión, y unir un valor entero a cada nodo que represente el tamaño de El sub-dag debajo del nodo más 1. Sin embargo, he estado atrapado durante varios días tratando de desarrollar el algoritmo que construye el diagrama de Hasse a partir del pedido parcial (¡no hablemos de incrementalidad!), Aunque pensé que sería algunos Material de pregrado estándar.

Aquí está mi estructura de datos:

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

Mi DAG se define mediante una lista de raíces y algún pedido parcial:

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

Estoy bastante atrapado aquí. Lo último que llegué para agregar un nuevo valor V al DAG es:

1. Encuentre todos los "subconjuntos raíz" RS_I de V en el DAG, es decir, subconjuntos de V tal que ningún superconjunto de RS_I es un subconjunto de V. Esto se puede hacer con bastante facilidad realizando una búsqueda (BFS o DFS) en el gráfico (collect función, posiblemente no óptima o incluso defectuosa).
2. Construya el nuevo nodo n_v, cuyos hijos son los RS_i encontrados anteriormente.
3. Ahora, descubramos dónde se debe conectar N_V: para una lista dada de raíces, descubra los superconjuntos de v. Si no se encuentra ninguno, agregue N_V a las raíces y elimine los subconjuntos de N_V de las raíces. De lo contrario, realice el paso 3 recursivamente en los hijos de los supersets.

Todavía no he implementado plenamente este algoritmo, pero parece que no es de acuerdo con circonuga y no óptima para mi problema aparentemente simple. ¿Hay algún algoritmo más simple disponible (Google no tenía idea de esto)?

Answer 1

Después de un poco de trabajo, finalmente terminé resolviendo mi problema, siguiendo mi intuición inicial. El método de recolección y la evaluación de rango fueron defectuosos, los reescribí con la recursión de la cola como una bonificación. Aquí está el código que obtuve:

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

Ahora debo verificar algo de optimización: - cortar ramas con conjuntos totalmente distintos al recolectar subconjuntos (como sugirió Rex Kerr) - vea si la clasificación de los conjuntos por tamaño mejora el proceso (como Mitchus sugirió)

El siguiente problema es trabajar la (peor) complejidad de la operación add (). Con N el número de conjuntos y D el tamaño del conjunto más grande, la complejidad probablemente será O (N²D), pero espero que pueda refinarse. Aquí está mi razonamiento: si todos los conjuntos son distintos, el DAG se reducirá a una secuencia de raíces/hojas. Por lo tanto, cada vez que trato de agregar un nodo a la estructura de datos, todavía tengo que verificar la inclusión con cada nodo ya presente (tanto en procedimientos de recopilación como de fijación). Esto conduce a 1 + 2 + ... + n = n (n + 1)/2 ∈ O (n²) verificaciones de inclusión.

Cada prueba de inclusión establecida es O (d), de ahí el resultado.

Answer 2

Supongamos que tu DAG G contiene un nodo v para cada conjunto, con atributos v.s (el conjunto) y v.count (el número de instancias del conjunto), incluido un nodo G.root con G.root.s = union of all sets (dónde G.root.count=0 Si este conjunto nunca ocurre en su colección).

Luego para contar el número de subconjuntos distintos de s Podrías hacer lo siguiente (en una mezcla bastardizada de Scala, Python y Pseudo-Code):

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

dónde

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

Sin embargo, en mi opinión, por razones de rendimiento, sería mejor abandonar este tipo de solución puramente funcional ... funciona bien en listas y árboles, pero más allá de eso se pone difícil.