Computing intersections uniques des sous-ensembles

Étant donné un ensemble S = {s _i: {z _j: z ∈ N}}, ce qui est un algorithme efficace pour calculer les ensembles uniques d'intersections de les sous-ensembles de S?Computing intersections uniques des sous-ensembles

Pour l'arrière-plan, je suis confronté à plusieurs versions de ce problème, certaines plus grandes que d'autres. Dans le plus petit | S | ≈ 1,000, | s _i | ≈ 10 000 et les valeurs sont des codes postaux.

petit exemple pour plus de clarté:

 
Input: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}} 
Output: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}

| S | = 4 et il y a 2 = 16 sous-ensembles de S. Cependant, il existe seulement cinq ensembles uniques d'intersections de sous-ensembles. Les quatre premiers sont les membres de S eux-mêmes. Le cinquième est {3}. L'ensemble vide est déjà membre de S. Les 10 autres intersections produisent également des ensembles vides.

Source

2013-04-04 Sim

Je pense que ce que vous cherchez est juste un algorithme d'intersection simple, jetez un oeil à [algorithme d'intersection linéaire] (http://stackoverflow.com/questions/4642172/computing-set-intersection-in- linéaire) – amas

@amas il y a 2^n sous-ensembles de S et S a plus de 1000 éléments. Un algorithme d'intersection O (n) n'aide pas. L'intersection n'est pas l'enjeu de l'OMI, c'est décider quelles intersections ne pas faire. – Sim

désolé 4 que, peut-être je n'ai pas compris le problème. Pouvez-vous donner plus de détails? – amas

est ici une étape de pré-traitement rapide qui pourrait être utile.

éléments d'appel x et y équivalents si, pour chaque ensemble de _i, soit les deux ou ni de x et y appartiennent à s _i. Simplifiez le problème en supprimant tous les éléments sauf un représentant de chaque classe d'équivalence. À la fin, étendez chaque représentant à sa classe. Pour simplifier, analyser les ensembles un par un tout en conservant une carte de chaque élément à une étiquette pour sa classe d'équivalence, où l'équivalence est déterminée par rapport aux ensembles traités jusqu'à présent. Au départ, tous les éléments sont dans la même classe, donc cette carte envoie chaque élément à la même étiquette. Pour traiter un ensemble, initialisez une carte vide de nouvelles étiquettes.Pour chaque élément x de l'ensemble, soit k l'étiquette actuelle de x. Si la clé k existe dans la nouvelle carte d'étiquette, alors la valeur correspondant à k devient la nouvelle étiquette de x. Sinon, nous attribuons une nouvelle étiquette et l'assignons à x et ajoutons un mappage de k à la nouvelle étiquette.

Voici l'exécution de votre saisie.

Initialement label = {1: a, 2: a, 3: a, 4: a, 5: a, 6: a, 7: a, 8: a, 9: a, 10: a} .
Scanner {}. Rien ne se passe.
Scanner {1}. Changer l'étiquette [1] en b.
Scan {2, 3}. Changer l'étiquette [2] et l'étiquette [3] à c.
Balayage {3, 4, 5, 6, 7, 8, 9, 10}. Changez l'étiquette [3] en d et étiquetez [4..10] en e. A la fin, label = {1: b, 2: c, 3: d, 4: e, 5: e, 6: e, 7: e, 8: e, 9: e, 10: e} . Sélectionnez 1 (b) et 2 (c) et 3 (d) et 4 (e) pour représenter leurs classes. Tous les autres sont supprimés.

Source

2013-04-04 13:30:10

Intéressant. Cela ne résout pas le problème, mais cela m'a donné une bonne idée d'un moyen d'aborder l'ensemble du problème d'une manière différente et donc j'attribuerai la réponse. – Sim

temps asymptotique Complexité:

n: nombre d'ensembles, qui va changer lors de l'exécution

m: la taille de l'ensemble moyen

Durée: T (Ensembles de recherche-assortis) x T (intersection) x SOMME {k} pour k: 1..n

Durée: 2m x 2m x 1/2 n (n + 1)

Durée: O (4 m^2 x 1/2 nx (n + 1)) ~ O (n^2 m^2)

de l'algorithme proposé:

FOR i: 1..n 
{ 

    FOR j: i..n 
    { 

     IF i = j THEN SKIP 

     INTERSECTION := FIND-INTERSECTION (SETS[i], SETS[j]) 

     IF INTERSECTION ⊄ SETS[] THEN ADD INTERSECTION TO SETS[] 

    } 

}

Source

2013-04-04 08:34:21

Computing intersections uniques des sous-ensembles

Répondre

Questions connexes