Trouver tous les sous-ensembles d’une liste

Cela générera le jeu que vous voulez, mais dans un ordre différent (je sortinge par ordre alphabétique à la fin, vous voudrez également sortinger par longueur).

Vous allez vous retrouver avec:

une ab abc abcd abcde abce … d de e

Donc, tous les sous-ensembles possibles (en dehors de la chaîne vide), tout en maintenant l’ordre de la liste d’origine

L’idée est d’append chaque élément à une liste croissante. A chaque nouvel élément, ajoutez-le d’abord, puis ajoutez-le à tous les éléments existants.

Alors, commencez par ‘a’.

Passez à «b». Ajoutez-le à la liste. Nous avons maintenant {‘a’, ‘b’}.

Ajoutez-le aux éléments existants, nous avons donc ‘ab’. Maintenant nous avons {‘a’, ‘b’, ‘ab’}.

Puis ‘c’ et ajoutez-le aux éléments existants pour obtenir ‘ac’, ‘bc’, ‘abc’: {‘a’, ‘b’, ‘ab’, ‘c’, ‘ac’, ‘bc’, abc’}. Donc, jusqu’à ce que nous ayons fini.

  ssortingng set = "abcde"; // Init list List subsets = new List(); // Loop over individual elements for (int i = 1; i < set.Length; i++) { subsets.Add(set[i - 1].ToString()); List newSubsets = new List(); // Loop over existing subsets for (int j = 0; j < subsets.Count; j++) { string newSubset = subsets[j] + set[i]; newSubsets.Add(newSubset); } subsets.AddRange(newSubsets); } // Add in the last element subsets.Add(set[set.Length - 1].ToString()); subsets.Sort(); Console.WriteLine(string.Join(Environment.NewLine, subsets)); 

si tout ce dont vous avez besoin sont des combinaisons d’éléments de votre liste d’origine, vous pouvez transformer le problème en ce qui suit: vous avez un tableau de bits de taille N et vous souhaitez rechercher tous les choix possibles pour les éléments du tableau. Par exemple, si votre liste d’origine est

abcde

alors votre tableau peut être

0 1 0 0 0

qui se traduit par une sortie de

b

ou le tableau peut être

1 0 1 1 0

qui retourne

acd

c’est un problème de récursivité simple qui peut être résolu en un temps O(2^n)

modifier en ajoutant un pseudo-code pour l’algorithme de récursivité:

 CreateResultSet(List currentResult, int step) { if (the step number is greater than the length of the original list) { add currentResult to list of all results return } else { add 0 at the end of currentResult call CreateResultSet(currentResult, step+1) add 1 at the end of currentResult call CreateResultSet(currentResult, step+1) } } for every item in the list of all results display the result associated to it (ie from 1 0 1 1 0 display acd) 

Voici du code que j’ai créé. Il construit une liste de toutes les chaînes possibles d’un alphabet, de longueur 1 à maxLength: (autrement dit, nous calculons les puissances de l’alphabet)

  static class SsortingngBuilder { public static List> CreateSsortingngs(List alphabet, int maxLength) { // This will hold all the ssortingngs which we create List> ssortingngs = new List>(); // This will hold the ssortingng which we created the previous time through // the loop (they will all have length i in the loop) List> lastSsortingngs = new List>(); foreach (T t in alphabet) { // Populate it with the ssortingng of length 1 read directly from alphabet lastSsortingngs.Add(new List(new T[] { t })); } // This holds the ssortingng we make by appending each element from the // alphabet to the ssortingngs in lastSsortingngs List> newSsortingngs; // Here we make ssortingng2 for each length 2 to maxLength for (int i = 0; i < maxLength; ++i) { newStrings = new List>(); foreach (List s in lastSsortingngs) { newSsortingngs.AddRange(AppendElements(s, alphabet)); } ssortingngs.AddRange(lastSsortingngs); lastSsortingngs = newSsortingngs; } return ssortingngs; } public static List> AppendElements(List list, List alphabet) { // Here we just append an each element in the alphabet to the given list, // creating a list of new ssortingng which are one element longer. List> newList = new List>(); List temp = new List(list); foreach (T t in alphabet) { // Append the element temp.Add(t); // Add our new ssortingng to the collection newList.Add(new List(temp)); // Remove the element so we can make another ssortingng using // the next element of the alphabet temp.RemoveAt(temp.Count-1); } return newList; } } 

quelque chose sur les lignes d’une boucle while étendue:

Cela fonctionnera avec n’importe quelle collection. J’ai modifié un peu la réponse de @ Sapp

  static List> GetSubsets(IEnumerable Set) { var set = Set.ToList(); // Init list List> subsets = new List>(); subsets.Add(new List()); // add the empty set // Loop over individual elements for (int i = 1; i < set.Count; i++) { subsets.Add(new List(){set[i - 1]}); List> newSubsets = new List>(); // Loop over existing subsets for (int j = 0; j < subsets.Count; j++) { var newSubset = new List(); foreach(var temp in subsets[j]) newSubset.Add(temp); newSubset.Add(set[i]); newSubsets.Add(newSubset); } subsets.AddRange(newSubsets); } // Add in the last element subsets.Add(new List(){set[set.Count - 1]}); //subsets.Sort(); return subsets; } 

** Ensuite, si j’ai un jeu de chaînes, je l’utilise comme: