Collection de jeux ne contenant pas de jeux qui sont un sous-ensemble d'une autre dans la collection

Question

Je suis à la recherche d'une structure de données abstraite qui représente une collection d'ensembles tels qu'aucun ensemble de la collection est un sous-ensemble d'un autre ensemble de la collection.

Cela signifie que sur les conditions d'insertion suivantes seront remplies:

A. L'insertion d'un élément qui est déjà un sous-ensemble d'un autre élément retournera la collection originale.

B. Insertion d'un élément qui est un sur-ensemble de tous les autres éléments se traduira par une collection avec le surensemble ajoutée et les sous-ensembles enlevés.

En supposant un ordre sur les éléments de l'ensemble, peut alors être utilisé un arbre préfixe pour représenter la collection. Cela permet la condition A à traiter très rapidement (il prend plus de vérifier l'état que ce serait d'insérer le sous-ensemble) réunion mais la condition B prend du temps.

Je me demande s'il y a la structure de données qui permet B à satisfaire rapidement aussi.

Answer 1

L'approche triviale serait de garder une liste d'ensembles et d'effectuer une recherche linéaire à travers que pour chaque ensemble entrant (test si l'entrée est un sous-ensemble).

Cela va évidemment dans le temps O (n) pour la recherche linéaire et la taille éventuellement O (m) pour la taille de l'ensemble entrant. Ainsi O (n * m) Temps total (nombre de jeux par rapport à la taille de chaque ensemble).

L'optimisation la plus évidente, bien sûr, est à l'index sur la taille des set. Ensuite, vous ne tester chaque jeu entrant par rapport à ceux qui sont de taille égale ou supérieure. (Un ensemble ne peut pas être un sous-ensemble d'un ensemble plus petit, duh!).

L'optimisation suivante qui vient à l'esprit est de créer dans l'index des éléments. Ainsi, pour chaque ensemble entrant que vous pouvez trouver l'intersection de chaque ensembles contenant chacun des éléments. En d'autres termes, si, pour voir entrant {a, b, c}, on trouve cet élément {a} existe dans les ensembles A, B et D, élément {b} existe dans B, E et F, et {c} existe dans a, B, Z et ... alors l'ensemble d'entrée est un sous-ensemble B (l'intersection de {a, B, D}, {B, E, F} et {a, B, Z}).

Alors, qui sonne comme O (m * log (n)) complexité pour moi. (Nous devons effectuer des recherches sur chaque élément hachés de chaque ensemble entrant). Insertions devraient également être du même ordre (insérer le nouveau ID de jeu dans chacune des cartes de l'élément). (Dans l'analyse Big-O 2 * O (m log (n)) réduit jusqu'à O (m log (n)), bien sûr).

Answer 2

Une idée triviale, qui travaillera en O (K), où K est la taille de l'élément ajouté.

• garder ensembles de quelque manière que tu veux
• maintenir la carte de set_id -> set_size
• maintenir la carte de l'objet -> set_id

A et B sont O (K).

Answer 3

Si les membres de votre ensembles A, B, ... sont mis en correspondance avec les nombres premiers distincts (et relativement), et à côté de chaque jeu vous stocker le produit de tous les membres comme p (A), p (B) etc. alors des sous-ensembles et surensembles peuvent être trouvés par le fait que p (X) est un facteur de p (Y) ou vice versa.

Vous pourriez finir avec quelques chiffres très importants, je suppose, mais il fonctionne en théorie.

Par exemple:

si [a b c d] -> [2 3 5 7], p (abc) = 30, p (abd) = 42, p (bc) = 15, p (abcd) = 210

Answer 4

Qu'est-ce un site Dorky! Je suis maintenant inscrit, donc peut-être en temps voulu pouvoir commenter des choses d'hier. Jusque-là, mais ...

@Stephen C: bien que je crois que mon anglais soit suffisant me semble avoir acquis une explicator: il a manqué morceaux, cependant, et son commentaire doit se lire comme suit:

---

  

@Stephen C: trouver les facteurs d'un   nombre arbitraire est en effet complet NP, mais ne sont pas pertinentes. le   question est de savoir si la plus petite des deux   nombres exactement divise la plus grande, une   opération simple module. Par exemple,   p (bc) = 15 est un diviseur de p (abcd) = 210,   si bc est un sous-ensemble de abcd (comme les ensembles abd   et abc).

     

Ajout d'un nouvel ensemble S à la collection existante de N ensembles est O (N), en supposant que la comparaison et la division des grands nombres prend à peu près en même temps quel que soit N.

     

Pour chaque entrée existante E dans la collection de jeux, arrêtez si p (S)   

p (E) et p (E) divise p (S) exactement. Ajouter S si vous arrivez à la fin de la collection. Un tableau   de bignums travailleraient.

---

@JL. Si vous voulez être mon harceleur sur place s'il vous plaît efforcer de 1) ajouter de la valeur 2) avec précision