Generador de combinación en Linq

¿Es posible crear algún Linq que genere una lista que contenga todas las combinaciones posibles de una serie de números?

Si ingresa “21” generaría una lista con los elementos:

list[0] = "21" list[1] = "22" list[2] = "11" list[3] = "12" 

(No necesariamente en ese orden)

Entiendo que puedes usar el rango para hacer cosas como:

 List letterRange = Enumerable.Range('a', 'z' - 'a' + 1).Select(i => (Char)i).ToList(); //97 - 122 + 1 = 26 letters/iterations 

Que genera el alfabeto de az. Pero parece que no puedo transferir este conocimiento para hacer un generador de combinación

He sido capaz de resolverlo con el siguiente código, pero parece demasiado voluminoso y estoy seguro de que se puede hacer con unas pocas líneas. Realmente se siente como una mala solución que he hecho.

Imagina que he llamado a GetAllCombinations("4321") si ayuda

 public static String[] GetAllCombinations(String s) { var combinations = new string[PossibleCombinations(s.Length)]; int n = PossibleCombinations(s.Length - 1); for (int i = 0; i < s.Length; i++) { String sub; String[] subs; if (i == 0) { sub = s.Substring(1); //Get the first number } else if (i == s.Length - 1) { sub = s.Substring(0, s.Length - 1); } else { sub = s.Substring(0, i) + s.Substring(i + 1); } subs = GetAllCombinations(sub); for (int j = 0; j < subs.Length; j++) { combinations[i * n + j] = s[i] + subs[j]; } } return combinations; } public static int PossibleCombinations(int n) //Combination possibilities. eg 1-2-3-4 have 24 different combinations { int result = 1; for (int i = 1; i <= n; i++) result *= i; return result; } 

Por lo que vale, prueba algo como esto:

 public static IEnumerable GetPermutations(string s) { if (s.Length > 1) return from ch in s from permutation in GetPermutations(s.Remove(s.IndexOf(ch), 1)) select string.Format("{0}{1}", ch, permutation); else return new string[] { s }; } 

Para el registro: la respuesta de Josh de la manera genérica:

 public static IEnumerable> GetPermutations(IEnumerable items) { if (items.Count() > 1) { return items.SelectMany(item => GetPermutations(items.Where(i => !i.Equals(item))), (item, permutation) => new[] { item }.Concat(permutation)); } else { return new[] {items}; } } 

Aquí está mi función de permutación y combinación usando Linq

 public static IEnumerable Prepend(this IEnumerable source, TSource item) { if (source == null) throw new ArgumentNullException("source"); yield return item; foreach (var element in source) yield return element; } public static IEnumerable> Permutate(this IEnumerable source) { if (source == null) throw new ArgumentNullException("source"); var list = source.ToList(); if (list.Count > 1) return from s in list from p in Permutate(list.Take(list.IndexOf(s)).Concat(list.Skip(list.IndexOf(s) + 1))) select p.Prepend(s); return new[] { list }; } public static IEnumerable> Combinate(this IEnumerable source, int k) { if (source == null) throw new ArgumentNullException("source"); var list = source.ToList(); if (k > list.Count) throw new ArgumentOutOfRangeException("k"); if (k == 0) yield return Enumerable.Empty(); foreach (var l in list) foreach (var c in Combinate(list.Skip(list.Count - k - 2), k - 1)) yield return c.Prepend(l); } 

Para el alfabeto de ADN ‘A’, ‘C’, ‘G’, ‘T’:

 var dna = new[] {'A', 'C', 'G', 'T'}; foreach (var p in dna.Permutate()) Console.WriteLine(String.Concat(p)); 

da

 ACGT ACTG AGCT AGTC ATCG ATGC CAGT CATG CGAT CGTA CTAG CTGA GACT GATC GCAT GCTA GTAC GTCA TACG TAGC TCAG TCGA TGAC TGCA 

y las combinaciones (k = 2) del alfabeto de ADN

 foreach (var c in dna.Combinate(2)) Console.WriteLine(String.Concat(c)); 

son

 AA AC AG AT CA CC CG CT GA GC GG GT TA TC TG TT 

Lo que estás buscando son en realidad permutaciones. En resumen, las permutaciones significan que el orden es relevante (es decir, 12 es diferente de 21) mientras que una combinación significa que el orden es irrelevante (12 y 21 son equivalentes). Para más información, ver Wikipedia.

Ver este hilo

En cuanto a hacer es en LINQ puro, eso suena como usar LINQ por el bien de usar LINQ.

Como otros han señalado, las soluciones en esta página generarán duplicados si alguno de los elementos es el mismo. La extensión Distinct () los eliminará, pero no es muy escalable, ya que normalmente provocará que se cruce todo el árbol de búsqueda. Recortarás considerablemente el espacio de búsqueda invocando durante el recorrido:

 private static IEnumerable Permute(string str) { if (str.Length == 0) yield return ""; else foreach (var index in str.Distinct().Select(c => str.IndexOf(c))) foreach (var p in Permute(str.Remove(index, 1))) yield return str[index] + p; } 

Para el ejemplo de cadena “bananabana”, esto da como resultado que se visiten 8,294 nodos, a diferencia de los 9,864,101 visitados cuando no se realiza el sacrificio cruzado.