Algorithme de fusion d'ensembles partageant au moins 2 éléments

Question

À partir d'une liste d'ensembles:

• S_1: [1, 2, 3, 4]
• S_2: [3, 4, 5, 6, 7]
• S_3: [8, 9, 10, 11]
• S_4: [1, 8, 12, 13]
• S_5: [6, 7, 14, 15, 16, 17]

Quel est le moyen le plus efficace de fusionner tous les ensembles partageant au moins 2 éléments? Je suppose que cela ressemble à un problème de composants connectés. Donc, le résultat serait:

• [1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)
• [8, 9, 10, 11]
• [1, 8, 12, 13] (S_4 partage 1 avec S_1 et 8 avec S_3, mais n'est pas fusionné car ils ne partagent qu'un seul élément chacun

La mise en oeuvre naïve est O (N ^ 2), où N est le nombre de jeux, ce qui est impossible pour nous. Cela devrait être efficace pour des millions d'ensembles.

Answer 1

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

Ma tête dit que c'est à propos de l'ordre (2N ln N). Prenez cela avec un grain de sel.

Answer 2

Si vous pouvez commander les éléments de l'ensemble, vous pouvez utiliser Mergesort le les ensembles. La seule modification nécessaire est de rechercher les doublons pendant la phase de fusion. S'il en trouve un, jetez simplement le duplicata. Puisque mergesort est O (n * log (n)), cela offrira une vitesse améliorée par rapport à l'algorithme naïf O (n ^ 2).

Cependant, pour être vraiment efficace, vous devez conserver un ensemble trié et le conserver afin que vous puissiez ignorer la phase de tri et aller directement à la phase de fusion.

Answer 3

Je ne vois pas comment cela peut être fait en moins de O (n ^ 2).

Chaque ensemble doit être comparé à un autre pour voir s’il contient 2 éléments partagés ou plus. Ce sont n * (n-1) / 2 comparaisons, donc O (n ^ 2), même si la vérification des éléments partagés prend un temps constant.

Dans le tri, l’implémentation naïve est O (n ^ 2), mais vous pouvez tirer parti de la nature transitive de la comparaison ordonnée (par exemple, vous savez que rien dans la partition inférieure de quicksort ne doit être comparé à rien dans la partition supérieure, comme cela a déjà été comparé au pivot). C’est ce qui fait que le tri est O (n * log n).

Cela ne s'applique pas ici. Donc, à moins que les ensembles ne contiennent quelque chose de spécial qui nous permette d'ignorer les comparaisons basées sur les résultats de comparaisons précédentes, il s'agira en général de O (n ^ 2).

Paul.

Answer 4

Remarque secondaire: cela dépend de la fréquence à laquelle cela se produit. Si la plupart des paires de jeux font partagent au moins deux éléments, il serait peut-être plus efficace de créer le nouveau jeu en même temps que la comparaison et de le jeter à la poubelle. correspondre à la condition. Si la plupart des paires ne ne partagent pas au moins deux éléments, le report de la construction du nouvel ensemble jusqu'à ce que la confirmation de la condition soit plus efficace.

Answer 5

Si vos éléments sont de nature numérique ou peuvent être ordonnés naturellement (vous pouvez par exemple attribuer une valeur telle que 1, 2, 42, etc.), je suggérerais d'utiliser un tri de base sur les ensembles fusionnés, et faites une deuxième passe pour saisir les éléments uniques.

Cet algorithme devrait être de O (n), et vous pouvez optimiser le tri de base à l’aide d’opérateurs de décalage au niveau du bit et de masques de bits. J'ai fait quelque chose de similaire pour un projet sur lequel je travaillais et cela fonctionne à merveille.