Combinaison d'une liste de listes de telle sorte que chaque combinaison a des éléments uniques

Question

D'accord, alors, j'ai une liste de listes, comme le titre le dit, et je veux faire des combinaisons de k listes dans lesquelles chaque liste a des éléments différents des autres.

Exemple:

J'ai la liste de listes suivante:

{ {1,2,3} , {1,11} , {2,3,6} , {6,5,7} , {4,8,9} }

Une combinaison valide de ces listes de taille 3 pourrait être:

{ {1,11}, {4,8,9} ,{6,5,7} }

Ceci n'est qu'UNE des combinaisons valides, ce que je veux retourner est une liste de toutes les combinaisons valides de K listes.

Une combinaison invalide serait:

{ {1,11} ,{2, 3, 6}, {6, 5, 7} } 

parce que l'élément 6 est présent dans la deuxième et troisième liste.

J'ai déjà un code qui fait cela mais il trouve simplement toutes les combinaisons possibles et vérifie si elles sont valides avant de les ajouter à une liste de résultats finale. Comme cette liste de listes est assez grande (153 listes), lorsque K devient plus grand, le temps pris est aussi ridiculement grand (à K = 5 cela me prend environ 10 minutes.)

Je veux voir s'il y a un moyen efficace de le faire. Ci-dessous se trouve mon code actuel (les listes que je veux combiner sont des attributs de la classe Item):

public void recursiveComb(List arr, int len,  int startPosition, Item[] result)
{
    if (len == 0)
    {            
        if (valid(result.ToList()))
        {                
          //Ici j'ajoute le résultat à la liste finale

          //valid est juste une fonction qui vérifie si une liste a des éléments en double dans une autre 
        }            
        return;
    }

    for (int i = startPosition; i <= arr.Count - len; i++)
    {       
        result[result.Length - len] = arr[i];
        recursiveComb(arr, len - 1,  i + 1, result);
    }
}

Answer 1

Utilisez un HashSet https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx pour suivre les éléments distincts lorsque vous construisez la sortie à partir des candidats dans la liste d'entrée de listes/tuples

Accumulez une liste de sortie de tuples non superposés en itérant à travers la liste d'entrée de tuples et évaluez chaque tuple en tant que candidat comme suit : Pour chaque tuple d'entrée, insérez chaque élément du tuple dans le HashSet. Si l'élément que vous essayez d'insérer est déjà dans l'ensemble, le tuple ne respecte pas la contrainte et doit être ignoré, sinon les éléments du tuple sont tous distincts de ceux déjà dans la sortie.

L'objet hashset maintient efficacement un registre des éléments distincts dans votre liste acceptée de tuples.

Answer 2

Si j'ai bien compris votre code, vous passez chaque list de votre entrée à la fonction recursiveComb(). qui ressemble à ceci

for(int i = 0; i < inputnestedList.Count; i++)
{
    recursiveComb();
   // À l'intérieur de recursiveComb(), vous utilisez une autre boucle for avec récursivité.
   // C'est ce que j'ai observé à partir de votre premier paramètre c.-à-d. List
}

Corrigez-moi si je me trompe

Cela donne une complexité temporelle supérieure à O(n^2)

---

Voici ma solution la plus simple, avec deux boucles for sans récursion.

List> x = new List>{ new List(){1,2,3} , new List(){1,11} , new List(){2,3,6} , new List(){6,5,7} , new List(){4,8,9} };
List> result = new List>();
var watch = Stopwatch.StartNew();

for (int i = 0; i < x.Count;i++)
{
    int temp = 0;
    for (int j = 0; j < x.Count; j++)
    {
        if (i != j && x[i].Intersect(x[j]).Any())
            temp++;
    }

    // Cette condition décide que les éléments de la ième liste sont disponibles dans d'autres listes
    if (temp <= 1)
        result.Add(x[i]);
}
watch.Stop();
var elapsedMs = watch.Elapsed.TotalMilliseconds;

Console.WriteLine(elapsedMs);

Maintenant, lorsque j'imprime le temps d'exécution, le résultat est

Temps d'exécution : 11.4628

Vérifiez le temps d'exécution de votre code. Si le temps d'exécution de votre code est supérieur au mien, vous pouvez le considérer comme un code efficace

Preuve du code : DotNetFiddler

Bon codage

Answer 3

Si j'ai bien compris votre problème, alors cela fonctionnera :

 /// 
        /// Obtenez des ensembles de listes uniques
        /// 
        /// 
        /// 
        public List> GetUniqueSets(List> sets )
        {
            List> cache = new List>();

            for (int i = 0; i < sets.Count; i++)
            {
                // ajouter au cache s'il est vide
                if (cache.Count == 0)
                {
                    cache.Add(sets[i]);
                    continue;
                }
                else
                {
                    // vérifier si l'élément actuel est déjà dans le cache et s'il interagit avec l'un des éléments du cache
                    var cacheItems = from item in cache where (item != sets[i] && item.Intersect(sets[i]).Count() == 0) select item;

                    // si ce n'est pas le cas, ajouter au cache
                    if (cacheItems.Count() == cache.Count)
                    {
                        cache.Add(sets[i]);
                    }

                }
            }

            return cache;

        }

Testé, c'est rapide et a pris 00:00:00.0186033 pour trouver des ensembles.