union / intersection de 2 ensembles, où chaque ensemble est défini par ses sous-ensembles

Question

Nous connaissons la définition de chaque ensemble à partir de l'union d'autres ensembles.

Par exemple

A = B union {1,2}

B = C union D

C = {5,6}

D = {5,7}

E = {4}

alors A = {1,2,5,6,7}

Une union E = {1,2,4,5,6,7}

Sont les algorithmes les plus efficaces pour le faire. Supposons que la hiérarchie des unions puisse être très profonde et que les sous-ensembles changent assez souvent (pas tant que ça). Je pense qu'il devrait exister des moyens de réduire au minimum le nombre de syndicats à faire.

Answer 1

Vous avez donc une hiérarchie immuable de unions d’ensembles changeants? Et comme dans votre exemple, vous n’êtes intéressé que par la valeur d’un ensemble?

Ensuite, aplatissez la hiérarchie. C'est-à-dire que dans votre exemple, vous parcourriez une fois la hiérarchie pour trouver l'ensemble des ensembles de modifications, l'union de ceux-ci, et stocker cet ensemble.

Pour vous dispenser de recalculer les unions chaque fois qu'un jeu de feuilles change, vous pouvez suivre pour chaque élément le nombre de jeux qu'il contient actuellement. Cela peut être mis à jour rapidement si un jeu de feuilles change et si ceux qui ne sont pas obligés de regarder les jeux de feuilles non modifiés. Ensuite, ces éléments avec le nombre de fréquences > 0 sont actuellement dans l'union.

Answer 2

Peut-être recherchez-vous une sorte de structure de données disjoint ?

Answer 3

Plusieurs questions sur cette affaire.

Première question: pendant combien de temps ce "script" est-il; / " programme " avoir à courir? Au cas où ce ne serait pas trop long, il pourrait s'avérer une bonne option de simplement stocker les unions précédentes et de vérifier le cache avant d'effectuer une action d'union. La mémoire n’est pas si chère de nos jours:).

Deuxième question à poser: les éléments sont-ils dans un certain ordre avant l’union? S'ils ne le sont pas, et qu'une liste est consultée plusieurs fois, il peut être très utile de trier une liste en premier (par exemple, vous pouvez prendre une décision lorsque vous êtes à mi-chemin d'une liste, par exemple). La Mergesort est une technique puissante permettant de joindre efficacement deux listes ordonnées.