Unisci insiemi di insiemi che contengono elementi comuni in Scala

Question

Voglio implementare una funzione in Scala, che, dato un insieme di insiemi di Ints, unirà ogni Set contenente che contiene uno o più elementi comuni.

Così, per esempio, data:

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 conterranno Set (Set (1,2,3,7), Set (8,10))

Quale sarebbe una bella, efficiente e funzionale se possibile, modo per farlo in Scala?

Answer 1

Il modo più efficace per fare questo sarà utilizzando strutture mutabili, ma lei ha chiesto un modo funzionale, quindi ecco qui:

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

(non testato, ha scritto questo per mezzo del telefono)

Answer 2

Questo è probabilmente solo una variante della risposta di samthebest, ma per il bene di varietà:

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

una versione che è in gran parte nello spirito della risposta di samthebest, ma (in base alla progettazione) meno profondamente idiomatica. Potrebbe essere più accessibile per chi è nuovo alla programmazione funzionale. (Sembra che dovremmo spremere tutto il possibile da un bel problema così.)

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

Tuttavia, la seguente alternativa ha il vantaggio di essere coda ricorsiva e, forse, anche fornendo un percorso più agevole per comprendere la risposta di samthebest:

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) 

Non rivendico nessuno di questi come superiore: utile solo come strumenti di apprendimento.

Answer 4

La soluzione concisa di Samthebest è molto soddisfacente nella sua semplicità ed eleganza, ma sto lavorando con un gran numero di set e ho bisogno di una soluzione più performante che sia ancora immutabile e scritta in buono stile funzionale.

Per 10.000 set con 10 elementi ciascuno (valori scelti casualmente da 0 a 750.000), la soluzione concisa di samthebest richiedeva una media di ~ 30 secondi sul mio computer, mentre la mia soluzione di seguito richiedeva in media ~ 400 ms.

(Nel caso qualcuno si chiedeva, l'insieme risultante per le cardinalità impostata sopra contiene ~ 3600 insiemi, con una media di ~ 26 elementi ciascuno)

Se chiunque può vedere eventuali miglioramenti ho potuto fare rispetto a stile o prestazione, per favore fatemelo sapere!

Ecco cosa mi è venuta:

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