Unión de todos los conjuntos de intersección

Question

Dada una lista de objetos con múltiples atributos que necesito para encontrar la lista de conjuntos creados por la unión de todos los subconjuntos de intersección.

En concreto estos son objetos persona, cada uno con muchos atributos. Necesito crear una lista de conjuntos de 'maestros' en base a un puñado de identificadores únicos tales como SSN, DLN, etc.

Por ejemplo, si la persona A y la persona B tienen el mismo número de seguro social que crear un conjunto i. Entonces, si la persona B y C tienen el mismo DLN, que crear un conjunto ii. Persona D y E tienen el mismo SSN pero (y todos los otros identificadores) no coincide con cualquiera de los identificadores de las personas A, B o C. Después de combinar todos los subconjuntos de intersección que terminaría con un conjunto con las personas A, B, C y otro conjunto con Personas D, e.

Este es el pseudo-código para mi solución. Tengo curiosidad por si alguien ya ha llegado con una forma más eficiente de la fusión de todos los posibles conjuntos de intersección. Tenga en cuenta que los enlaces entre los conjuntos podrían ser X Personas largo (es decir, A Partidos B por SSN y B coincide C por DLN y C partidos D por SSN y D partidos E por algún otro identificador que resultaría de personas A-E en un sistema). Supongamos también que el lenguaje esta se llevará a cabo en soportes establece operaciones.

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end

Answer 1

Para ampliar mi comentario en el post original, que desea crear una lista de conjuntos, donde cada miembro de un determinado conjunto de acciones al menos un atributo con al menos otro miembro de ese conjunto.

Ingenuamente, esto se puede solucionar ya sea mediante la búsqueda de todos los pares que comparten un atributo y la fusión de pares juntos que tienen la misma pareja de forma iterativa. Esto sería O (N ^ 3) (N ^ 2 para iterar a través de pares, y hasta N conjuntos separados para determinar la pertenencia).

También puede pensar en este problema, ya que la determinación de la href="http://en.wikipedia.org/wiki/Connected_component_(graph_theory)" rel="nofollow noreferrer"> componente , donde cada objeto y cada valor de atributo único es un nodo; cada objeto estaría conectado a cada uno de sus valores de atributo. La creación de ese gráfico tomaría tiempo lineal, y se podía determinar los componentes conectados en tiempo lineal con una anchura o profundidad primera búsqueda.

Answer 2

Me imagino que usted tiene un conjunto relativamente pequeño de los atributos del objeto Person (en comparación con el número de la persona que los objetos que está considerando). Si desea reducir recorrer la lista de objetos persona varias veces, se puede tomar una persona, poner sus atributos en una lista de posibles conexiones conocidas y luego pasar a la siguiente persona. Con cada persona sucesiva, se ve si está conectado a cualquier conexión anterior. Si es así, a continuación, agregar sus atributos únicos de las posibles conexiones. Usted debe ser capaz de procesar todos los objetos Persona en una sola pasada. Es posible que usted tendrá algunos conjuntos desconectados en los resultados, por lo que puede valer la pena examinar los objetos persona ajena después de haber creado el primer gráfico.

Answer 3

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

Answer 4

En primer lugar, ¿existe alguna jerarquía inherente a los identificadores, y no en contradicción con los identificadores de un mayor tipo anular el mismo identificador de una especie inferior? Por ejemplo, si A y B tienen el mismo SSN, B y C tienen el mismo DLN, y C y D tienen el mismo SSN que no coincide con A y el SSN de B, ¿quiere decir que hay dos grupos o una?

Suponiendo contradicciones no importan, se trata de clases de equivalencia, como usuario 57368 (desconocidos) de Google estados. Para las clases de equivalencia, las personas a menudo recurren a la estructura de unión-. En cuanto a la forma de realizar estas uniones, no es trivial, ya que de inmediato Asumo que no tienen el enlace directo A-B cuando A y B tienen el mismo número de seguro social. En cambio, nuestros conjuntos constarán de dos tipos de elementos. Cada par (attribute type, attribute value) = attribute es un elemento. También tiene elementos que corresponden a objects. Al iterar a través de la lista de atributos de un objeto, realizar la unión (object, attribute).

Una de las características importantes de la estructura de datos de la Unión-encontrar es que la estructura resultante representa el conjunto. Se le permite consultar "¿Qué conjunto es A en?" Si esto no es suficiente, háganoslo saber y podemos mejorar el resultado.

Sin embargo, la característica más importante es que el algoritmo tiene algo que se asemeja a un comportamiento constante de tiempo para cada operación de unión y de consulta.

Answer 5

Por lo que su recolección ejemplo podría tener este aspecto:

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

A continuación, me permito sugerir el uso de un algoritmo que se acumulan múltiples colecciones mediante la fusión de forma incremental o la inserción de cada colección en las múltiples colecciones:

La iteración 1. La primera colección se convierte en el único multi-colección:

{A} { ss |-> [42], dl |-> [123] }

iteración 2. Combinar la siguiente colección en la primera desde SSN ya está presente:

{A,B} { ss |-> [42], dl |-> [123,456] }

iteración 3. Combinar de nuevo, ya que el DLN ya está ahí:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

La iteración 4. Insertar un nuevo multi-colección ya no hay ninguna coincidencia:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

La iteración 5. fusionarse con la segunda colección de varios, ya que el SSN está ahí:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

Así que en cada iteración (uno para cada colección), debe identificar todos de múltiples colecciones que tienen valores en común con la colección que se está procesando, y se funden todos estos juntos.

En general, si hay n colecciones cada uno con un número constante k de atributos, a continuación, este algoritmo se ejecuta en el tiempo O (NNK) = O (n ² ). El comportamiento peor de los casos se exibited si todos los valores de los atributos son distintos. Cuando hay un mayor intercambio entre los valores de los atributos, el tiempo que se necesita para insertar y determinar la pertenencia a los conjuntos de valores de atributos (como [23,42]) llega a ser el factor dominante, por lo que los conjuntos de valores de atributo debe ser eficiente.

Si utiliza conjuntos disjuntos óptimas , entonces cada Encontrar o fusionar la operación se ejecutará en el tiempo amortizado O (α (n)).

Por lo tanto, para cada iteración habrá a lo sumo n multi-colecciones (la situación cuando hay múltiples colecciones se han fusionado hasta ahora). Para integrar la nueva colección en las múltiples colecciones, que tendrá que realizar una operación de búsqueda en cada una de las múltiples colecciones k conjuntos para identificar todos los multi-colecciones que se fusionen, lo cual lleva tiempo limitado por O (nkα (n)) . Para combinar la en la mayoría de k multi-colecciones conocer de esta manera toma O (k ² α (n)).

Así que para todos iteración el tiempo está limitada por O (n (nkα (n) + k ² α (n))) = O (n (nkα (n))) = O ( n ² Ka (n)) = O (n ² α (n)) ya que k es una constante.

Debido α (n) para todos los fines prácticos es también una constante, el tiempo total está limitada por O (n ² ).