Verschmelzen Sets von Sets, die gemeinsame Elemente in Scala enthalten

Question

Ich möchte eine Funktion in Scala implementieren, die bei einem Satz von Sets von Ints alle enthaltenen Sets zusammenführt, die ein oder mehrere gemeinsame Elemente enthalten.

So zum Beispiel gegeben:

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = ??? 

val sets = Set(Set(1,2), Set(2,3), Set(3,7), Set(8,10)) 
val mergedSets = mergeSets(sets) 

mergedSets enthalten Set (Set (1,2,3,7), Set (8,10))

Was für ein schöner wäre, effizient und funktionell wenn möglich, wie geht das in Scala?

Answer 1

Der effizienteste Weg, dies zu tun, wird veränderbare Strukturen verwenden, aber Sie für eine funktionelle Art und Weise gefragt, geht so hier:

sets.foldLeft(Set.empty[Set[Int]])((cum, cur) => { 
    val (hasCommon, rest) = cum.partition(_ & cur nonEmpty) 
    rest + (cur ++ hasCommon.flatten) 
}) 

(Nicht geprüft, dies mit Telefon schrieb)

Answer 2

Diese eine Variante von samthebest Antwort ist wahrscheinlich nur, aber im Interesse der Vielfalt:

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = { 
    def hasIntersect(set: Set[Int]): Boolean = 
     sets.count(set.intersect(_).nonEmpty) > 1 

    val (merged, rejected) = sets partition hasIntersect 
    Set(merged.flatten, rejected.flatten) 
    } 

Answer 3

eine Version, die weitgehend im Geist der samthebest Antwort ist, aber (mit Absicht) weniger tief idiomatische. Es kann für diejenigen, die neu in der funktionalen Programmierung sind, zugänglicher sein. (Es scheint, wir sollten alles quetschen wir aus so einem schönen Problem können.)

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = { 
    if (sets.isEmpty) { 
    Set.empty[Set[Int]] 
    } else { 
    val cur = sets.head 
    val merged = mergeSets(sets.tail) 
    val (hasCommon, rest) = merged.partition(_ & cur nonEmpty) 
    rest + (cur ++ hasCommon.flatten) 
    } 
} 

jedoch die folgende Alternative hat den Vorteil, dass sie Schwanz rekursive und vielleicht auch einen glatteren Weg bietet samthebest Antwort auf Verständnis:

def mergeSets(cum: Set[Set[Int]], sets: Set[Set[Int]]): Set[Set[Int]] = { 
    if (sets.isEmpty) { 
    cum 
    } else { 
    val cur = sets.head 
    val (hasCommon, rest) = cum.partition(_ & cur nonEmpty) 
    mergeSets(rest + (cur ++ hasCommon.flatten), sets.tail) 
    } 
} 

def mergeSets(sets: Set[Set[Int]]): Set[Set[Int]] = 
    mergeSets(Set.empty[Set[Int]], sets) 

Ich behaupte nicht, dass eine dieser beiden als überlegen: nur als Lernwerkzeuge nützlich.

Answer 4

Samthebests knappe Lösung ist sehr befriedigend in ihrer Einfachheit und Eleganz, aber ich arbeite mit einer großen Anzahl von Sets und brauchte eine performantere Lösung, die immer noch unveränderlich und in einem guten funktionalen Stil geschrieben ist.

Für 10.000 Sets mit je 10 Elementen (zufällig ausgewählte Werte von 0 bis 750.000) benötigte samtests knappe Lösung durchschnittlich ~ 30 Sekunden auf meinem Computer, während meine Lösung im Durchschnitt ~ 400 ms dauerte.

(Falls jemand fragt mich, der resultierende Satz für den obigen Satz Mächtigkeiten enthält ~ 3600 Sets, mit einem Durchschnitt von ~ 26 Elementen jeweils)

Wenn jemand irgendwelche Verbesserungen sehen kann ich in Bezug auf Stil machen könnte oder Leistung, lass es mich wissen!

Hier ist, was ich kam mit:

val sets = Set(Set(1, 2), Set(2, 3), Set(4, 5)) 
Association.associate(sets) => Set(Set(1, 2, 3), Set(4, 5)) 


object Association { 

    // Keep track of all current associations, as well as every element in any current association 
    case class AssociationAcc[A](associations: Set[Set[A]] = Set.empty[Set[A]], all: Set[A] = Set.empty[A]) { 
    def +(s: Set[A]) = AssociationAcc(associations + s, all | s) 
    } 

    // Add the newSet to the set associated with key A 
    // (or simply insert if there is no such key). 
    def updateMap[A](map: Map[A, Set[A]], key: A, newSet: Set[A]) = { 
    map + (key -> (map.getOrElse(key, Set.empty) ++ newSet)) 
    } 

    // Turn a Set[Set[A]] into a map where each A points to a set of every other A 
    // it shared any set with. 
    // 
    // e.g. sets = Set(Set(1, 2), Set(2, 3), Set(4, 5)) 
    //  yields: Map(1 -> Set(2), 2 -> Set(1, 3), 3 -> Set(2), 
    //     4 -> Set(5), 5 -> Set(4)) 
    def createAssociationMap[A](sets: Set[Set[A]]): Map[A, Set[A]] = { 
    sets.foldLeft(Map.empty[A, Set[A]]) { case (associations, as) => 
     as.foldLeft(associations) { case (assoc, a) => updateMap(assoc, a, as - a) } 
    } 
    } 

    // Given a map where each A points to a set of every A it is associated with, 
    // and also given a key A starting point, return the total set of associated As. 
    // 
    // e.g. with map = Map(1 -> Set(2), 2 -> Set(1, 3), 3 -> Set(2), 
    //      4 -> Set(5), 5 -> Set(4)) 
    // and key = 1 (or 2 or 3) yields: Set(1, 2, 3). 
    // with key = 4 (or 5) yields: Set(4, 5) 
    def getAssociations[A](map: Map[A, Set[A]], key: A, hit: Set[A] = Set.empty[A]): Set[A] = { 
    val newAssociations = map(key) &~ hit 
    newAssociations.foldLeft(newAssociations | hit + key) { 
     case (all, a) => getAssociations(map, a, all) 
    } 
    } 

    // Given a set of sets that may contain common elements, associate all sets that 
    // contain common elements (i.e. take union) and return the set of associated sets. 
    // 
    // e.g. Set(Set(1, 2), Set(2, 3), Set(4, 5)) yields: Set(Set(1, 2, 3), Set(4, 5)) 
    def associate[A](sets: Set[Set[A]]): Set[Set[A]] = { 
    val associationMap = createAssociationMap(sets) 
    associationMap.keySet.foldLeft(AssociationAcc[A]()) { 
     case (acc, key) => 
     if (acc.all.contains(key)) acc 
     else      acc + getAssociations(associationMap, key) 
    }.associations 
    } 
}