Generieren Sie eine DAG aus einem Poset unter Verwendung einer strengen funktionellen Programmierung

Question

Hier ist mein Problem: Ich habe eine Sequenz von (nicht leerer, aber möglicherweise nicht unterschiedlicher) Sets s_i, und für jeden S_I muss wissen, wie viele Sets s_j in s (i ≠ j) Untergruppen von S_I sind.

Ich brauche auch eine inkrementelle Leistung: Sobald ich alle meine Zählungen habe, kann ich einen Satz S_I durch eine Teilmenge von S_I ersetzen und die Zählungen schrittweise aktualisieren.

All dies mit rein funktionellem Code durchzuführen, wäre ein großes Plus (ich Code in Scala).

Da die Einbeziehung eine teilweise Bestellung ist, dachte ich, der beste Weg, mein Problem zu lösen Die Unterabteilung unter dem Knoten plus 1. Ich bin jedoch seit mehreren Tagen versucht, den Algorithmus zu entwickeln, der das HASSE-Diagramm aus der Teilbestellung aufbaut (lassen Sie uns nicht über Inkrementalität sprechen!), Auch ich dachte Standardmaterial.

Hier ist meine Datenstruktur:

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

Meine DAG wird durch eine Liste von Wurzeln und eine teilweise Bestellung definiert:

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

Ich stecke hier ziemlich fest. Das letzte Mal, dass ich der DAG einen neuen Wert V hinzufügte, ist:

1. Finden Sie alle "Root -Untergruppen" RS_I von V in der DAG, dh Teilmengen von V, so dass kein Superset von RS_I eine Teilmenge von v ist. Dies kann durch eine Suche (BFS oder DFS) im Diagramm (BFS oder DFS) (BFS oder DFS) (BRAGE) einfach durchgeführt werden.collect Funktion, möglicherweise nicht optimal oder sogar fehlerhaft).
2. Erstellen Sie den neuen Knoten n_v, dessen Kinder zuvor gefunden wurden.
3. Lassen Sie uns nun herausfinden, wo N_V angehängt werden soll: Für eine bestimmte Liste von Wurzeln finden Sie Supersets von v. Wenn keine gefunden werden, fügen Sie N_V zu den Wurzeln hinzu und entfernen Sie Teilmengen von N_V aus den Wurzeln. Andernfalls führen Sie Schritt 3 rekursiv mit den Kindern der Supersets durch.

Ich habe diesen Algorithmus noch nicht vollständig implementiert, aber er scheint für mein scheinbar einfaches Problem ungewöhnlich verteilt und nicht optimal zu sein. Gibt es einen einfacheren Algorithmus (Google war dabei ahnungslos)?

Answer 1

Nach einiger Arbeit löste ich schließlich mein Problem nach meiner ersten Intuition. Die Sammelmethode und die Rangbewertung waren fehlerhaft, ich habe sie mit Schwanzrezision als Bonus neu geschrieben. Hier ist der Code, den ich erhalten habe:

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

Ich muss jetzt einige Optimierung überprüfen: - Abzweigungen mit völlig unterschiedlichen Sätzen beim Sammeln von Teilmengen (wie Rex Kerr vorgeschlagen) - prüfen Sie, ob die Sortierung der Sets nach Größe den Prozess verbessert (wie Mitchus vorgeschlagen)

Das folgende Problem besteht darin, die (schlimmste) Komplexität des add () -Operationsvorgangs auszuarbeiten. Bei n der Anzahl der Sets und D der Größe des größten Satzes wird die Komplexität wahrscheinlich O (n²d) sein, aber ich hoffe, dass sie verfeinert werden kann. Hier ist meine Argumentation: Wenn alle Sätze unterschiedlich sind, wird die DAG auf eine Abfolge von Wurzeln/Blättern reduziert. Jedes Mal, wenn ich versuche, der Datenstruktur einen Knoten hinzuzufügen, muss ich immer noch auf die Einbeziehung mit jedem bereits vorhandenen Knoten suchen (sowohl in den Sammlungs- als auch in Anhängen von Verfahren). Dies führt zu 1 + 2 +… + n = n (n + 1)/2 ∈ O (n²) Einschlussprüfungen.

Jeder eingestellte Einschluss -Test ist O (D), daher das Ergebnis.

Answer 2

Nehmen Sie an, Ihre Dag G Enthält einen Knoten v für jeden Satz mit Attributen v.s (der Satz) und v.count (Die Anzahl der Instanzen des Satzes), einschließlich eines Knotens G.root mit G.root.s = union of all sets (wo G.root.count=0 Wenn dieses Set in Ihrer Sammlung niemals vorkommt).

Dann die Anzahl der unterschiedlichen Teilmengen von zu zählen s Sie können Folgendes machen (in einer bastardisierten Mischung aus Scala, Python und Pseudo-Code):

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

wo

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

Meiner Meinung nach wären Sie aus Leistungsgründen besser, diese Art von rein funktionierender Lösung aufzugeben ... es funktioniert gut auf Listen und Bäumen, aber darüber hinaus wird das Gehen hart.