Generar un DAG desde un poset utilizando estrictamente la programación funcional

Question

Aquí está mi problema: Tengo una secuencia S de (no vacíos pero posiblemente no distintos) establece 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 tenga todos mis conteos, puedo reemplazar un conjunto s_i por un subconjunto de s_i y actualizar los recuentos de forma incremental.

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

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

Aquí es 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 por una lista de raíces y un poco de orden 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 atascado aquí. La última vez que vine para añadir un nuevo valor v para el DAG es:

1. encuentra toda rs_i "subconjuntos de raíz" 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 bastante fácilmente realizando una búsqueda (BFS o DFS) en el gráfico (función collect, posiblemente no óptima o incluso defectuosa).
2. construye el nuevo nodo n_v, cuyos hijos son los previamente encontrados rs_i.
3. Ahora, descubramos dónde debe adjuntarse n_v: para una lista dada de raíces, descubra los superconjuntos de v. Si no 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 superconjuntos.

Todavía no he implementado completamente este algoritmo, pero parece ser intrincado y no óptimo para mi problema aparentemente simple. ¿Hay algún algoritmo más simple disponible (Google no tenía ni idea de esto)?

Answer 1

Después de un trabajo, finalmente terminé resolviendo mi problema, siguiendo mi intuición inicial. El método de recopilación y la evaluación de rango fueron defectuosos, los reescribí con recursión de 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 comprobar alguna optimización: - cortar ramas con juegos totalmente distintos en la recogida de subconjuntos (como se sugiere Rex Kerr) - ver si la clasificación de los conjuntos por tamaño mejora la proceso (como se sugirió mitch)

El siguiente problema es resolver la (peor de los casos) complejidad de la operación add(). Con n el número de conjuntos, yd el tamaño del conjunto más grande, la complejidad probablemente será O (n²d), pero espero que se pueda refinar. 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, aún tengo que verificar la inclusión con cada nodo ya presente (tanto en procedimientos de recopilación como de adjuntar). Esto conduce a controles de inclusión 1 + 2 + ... + n = n (n + 1)/2 ∈ O (n²).

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

Answer 2

Suponga que su 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), incluyendo un nodo de G.root con G.root.s = union of all sets (donde G.root.count=0 si este conjunto nunca ocurre en tu colección).

A continuación, para contar el número de subconjuntos distintos de s que podría hacer lo siguiente (en una mezcla bastarda de Scala, Python y pseudo-código):

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

donde

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

En mi opinión, sin embargo, por razones de rendimiento sería mejor que abandones este tipo de solución puramente funcional ... funciona bien en listas y árboles, pero más allá de eso, las cosas se ponen difíciles.