União de Conjuntos Todos interseção

Question

Dada uma lista de objetos com vários atributos que eu preciso para encontrar a lista de conjuntos criados por uma união de todos os subconjuntos de intersecção.

Especificamente estas são Person objetos, cada um com muitos atributos. Eu preciso criar uma lista de conjuntos de 'mestre' com base em um punhado de identificadores exclusivos, como SSN, DLN, etc.

Por exemplo, se a pessoa A e Pessoa B têm o mesmo SSN eles criam um conjunto i. Então, se a pessoa B e C têm a mesma DLN, eles criam um ii set. Pessoa D e E têm o mesmo SSN mas (e todos os outros identificadores) não coincide com qualquer um dos identificadores de pessoas A, B ou C. Após a fusão todos os subconjuntos que se intersectam gostaria acabam com um conjunto com pessoas A, B, C e um outro conjunto com Pessoas D, e.

Aqui está o código pseudo para a minha solução. Estou curioso, se alguém já veio acima com uma maneira mais eficiente de fundir todos os possíveis conjuntos de intersecção. Tenha em atenção que as ligações entre as séries pode ser X Pessoas longo (isto é, A corresponde a B por SSN e B corresponde a C por DLN e C corresponde a D por SSN e D corresponde a E por algum outro identificador iria resultar de Pessoas A-E em um conjunto). Também assumem que a linguagem este será implementado em suportes operações definidas.

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 expandir no meu comentário no post original, que pretende criar uma lista de conjuntos em que cada membro de uma dada ações definidas pelo menos um atributo com pelo menos um outro membro desse conjunto.

Ingenuamente, isso pode ser resolvido ou pela descoberta de todos os pares que compartilham um atributo e fundindo pares junto que têm o mesmo parceiro de forma iterativa. Este seria O (N ^ 3) (N ^ 2 para a iteração sobre pares, e até N conjuntos separados para determinar a associação).

Você também pode pensar este problema como determinar o componente conectado de um gráfico , onde cada objeto e cada valor do atributo único é um nó; cada objecto seria ligado a cada um dos seus valores de atributo. Configurar esse gráfico levaria tempo linear, e você poderia determinar os componentes conectados em tempo linear com uma amplitude ou profundidade primeira pesquisa.

Answer 2

Eu acho que você tem um conjunto relativamente pequeno de atributos para o objeto Pessoa (em comparação com o número de objetos Person você está pensando). Se você quiser reduzir a percorrer a lista de objetos Person várias vezes, você pode levar uma pessoa, colocar seus atributos em uma lista de conexões possíveis conhecidos e, em seguida, passar para a próxima pessoa. Com cada pessoa sucessiva, você ver se ele está ligado a qualquer conexão prévia. Se sim, então você adicionar seus atributos únicos para as possíveis conexões. Você deve ser capaz de processar todos os objetos Pessoa em uma passagem. É possível que você vai ter alguns conjuntos desconexos nos resultados, então pode valer a pena examinar a Pessoa desconectados objetos depois de ter criado o primeiro 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

Em primeiro lugar, há alguma hierarquia inerente identificadores, e não contraditórias identificadores de um maior tipo cancelar o mesmo identificador de um tipo mais baixo? Por exemplo, se A e B têm o mesmo SSN, B e C têm o mesmo DLN, e C e D têm o mesmo SSN que não corresponde de A e B SSN, isso significa que há dois grupos ou uma?

Assumindo contradições não importa, você está lidando com classes de equivalência, como usuário 57368 estados (desconhecidos Google). Para as classes de equivalência, as pessoas muitas vezes se voltam para o União-encontrar estrutura . Quanto à forma de executar essas uniões, não é imediatamente trivial porque eu suponho que você não tem o link direto A-B quando ambos A e B têm o mesmo SSN. Em vez disso, nossos conjuntos será composta de dois tipos de elementos. Cada par (attribute type, attribute value) = attribute é um elemento. Você também tem elementos correspondentes a objects. Quando você percorrer a lista de atributos para um objeto, execute o (object, attribute) união.

Uma das características importantes da estrutura de dados Union-descoberta é que a estrutura resultante representa o conjunto. Ele permite que você consulta "O conjunto é um in?" Se isso não for suficiente, avise-nos e podemos melhorar o resultado.

Mas a característica mais importante é que o algoritmo tem algo que se assemelha a um comportamento de tempo constante para cada operação de união e de consulta.

Answer 5

Portanto, o seu exemplo coleção poderia ser assim:

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 }

Então eu sugiro usar um algoritmo onde você constrói-se multi-coleções por incrementalmente fusão ou inserindo cada coleção para as multi-coleções:

A iteração 1. A primeira coleção torna-se o único multi-coleção:

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

A iteração 2. Fundir a próxima coleção para o primeiro desde SSN já está presente:

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

A iteração 3. Mesclar novamente, uma vez que o DLN já está lá:

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

Iteração 4. Insira um novo multi-coleção já que não há jogo:

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

A iteração 5. Mesclar com o segundo vários coleção, desde o SSN está lá:

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

Assim, em cada iteração (um para cada coleção), você deve identificar todas multi-coleções que têm valores em comum com a coleção que você está processando, e merge todas estes juntos.

De uma maneira geral, se existem n colecções cada um com um número constante k de atributos, em seguida, este algoritmo será executado em tempo O (NNK) = O (n ² ). O comportamento de pior caso é exibited se todos os valores de atributos são distintos. Quando há mais partilha entre valores de atributos, o tempo que leva para inserir e determinar a associação nos conjuntos de valores atributo (como [23,42]) chega a ser o fator dominante, de modo que os conjuntos de valores atributo deve ser eficiente.

Se você usar ideal conjuntos disjuntos , então cada operação Localizar ou mesclar será executado em tempo O amortizado (a (n)).

Assim, para cada iteração haverá no máximo n multi-coleções (a situação quando há múltiplas coleções foram fundidas até agora). Para integrar a nova coleção para as multi-coleções, você terá que executar uma operação de localizar em cada um dos multi-coleções k conjuntos para identificar todos os multi-coleções para ser incorporada, o que leva tempo limitado por O (nka (n)) . Para fundir o na maioria dos conjuntos de multi-k encontrado desta forma leva O (k ² a (n)).

Portanto, para todos iteração do tempo é delimitada por O (N (nka (n) + k ² a (n))) = O (n (nka (n))) = O ( n ² K? (n)) = O (n ² a (n)) uma vez que k é uma constante.

Como a (n) para todos os efeitos práticos é também uma constante, o tempo total é delimitada por O (N ² ).