Recherche d'ensembles chevauchants

Question

J'écris un système Digital Fountain en C#. Une partie de ce système me crée des ensembles d'entiers, j'ai besoin de trouver les combinaisons d'ensembles qui créent peuvent me laisser avec un ensemble d'un seul élément. Quel est le moyen le plus rapide de le faire?

Set A: 1,2,3,4,5,6 
Set B: 1,2,3,4,6 
Set C: 1,2,3 
Set D: 5,6 

Solutions: 
A - B => 5 
A - (C + D) => 4 

Je ne ai pas besoin de trouver toutes les combinaisons, juste assez pour me trouver autant de numéros uniques que possible. Cela peut être possible d'exploiter pour créer un algorithme plus efficace. Un point important que j'ai oublié de mentionner: Je ne sais pas, au préalable, combien il y a d'ensembles, à la place je les ajoute un par un, et je dois déterminer chaque fois si j'ai trouvé tous les nombres dont j'ai besoin. L'algorithme doit donc être quelque chose qui peut être exécuté par étapes à mesure que de nouveaux ensembles sont ajoutés.

Nb. Solutions en C# obtenir des marques bonus;)

Answer 1

Je pense que quelques bonnes solutions peuvent être gagnées par une sorte de modification de l'utilisation de l'algorithme de couverture d'ensemble gourmand (http://en.wikipedia.org/wiki/Set_cover_problem).

[pseudocode] donc:

1. sort sets by size descending 
2. 
foreach set in sets do: 
    uncovered = set.size 
    while uncovered > 1 
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set 
    uncovered = uncovered - covered_by_set(set) 
    collect current_set to some array 
    end 
end 

modifier:

• vous pouvez ommettre boucle foreach pour le dernier mis
• cela vous apportera pas plus d'une solution pour chacun des ensembles (pour fixer ceci vous pouvez changer le problème directement dans le problème de couverture de jeu et utiliser gourmand ensemble couverture), par exemple si vous tableau [1,3,4], vous devez trouver la solution de SCV problème pour tous les sous-ensembles de celui-ci qui ont la taille = 2: [1 , 3], [1,4], [3,4]. il fera problème beaucoup plus complexe
• une autre façon que vous pouvez envisager sont algorithmes d'évolution (représentation ici sera très simple, traiter nombre spécifié comme bit, la fonction de remise en forme devrait se rapprocher de 1), mais encore ne résoudre le problème de ne pas ajouter nouvel ensemble après les calculs (peut-être quand vous avez la meilleure population de dernier problème, puis après avoir ajouté nouvel ensemble juste ajouter une nouvelle place dans chromosome)