¿Cuál es la mejor manera de encontrar todas las combinaciones de elementos en una matriz?

¿Cuál es la mejor manera de encontrar todas las combinaciones de elementos en una matriz en c #?

¡Está en!)

static List> comb; static bool[] used; static void GetCombinationSample() { int[] arr = { 10, 50, 3, 1, 2 }; used = new bool[arr.Length]; used.Fill(false); comb = new List>(); List c = new List(); GetComb(arr, 0, c); foreach (var item in comb) { foreach (var x in item) { Console.Write(x + ","); } Console.WriteLine(""); } } static void GetComb(int[] arr, int colindex, List c) { if (colindex >= arr.Length) { comb.Add(new List(c)); return; } for (int i = 0; i < arr.Length; i++) { if (!used[i]) { used[i] = true; c.Add(arr[i]); GetComb(arr, colindex + 1, c); c.RemoveAt(c.Count - 1); used[i] = false; } } } 

ACTUALIZADO

Aquí hay un conjunto de funciones genéricas (requieren .net 3.5 o superior) para diferentes escenarios. Las salidas son para una lista de {1, 2, 3, 4} y una longitud de 2.

Permutaciones con repetición

 static IEnumerable> GetPermutationsWithRept(IEnumerable list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetPermutationsWithRept(list, length - 1) .SelectMany(t => list, (t1, t2) => t1.Concat(new T[] { t2 })); } 

Salida:

 {1,1} {1,2} {1,3} {1,4} {2,1} {2,2} {2,3} {2,4} {3,1} {3,2} {3,3} {3,4} {4,1} {4,2} {4,3} {4,4} 

Permutaciones

 static IEnumerable> GetPermutations(IEnumerable list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetPermutations(list, length - 1) .SelectMany(t => list.Where(o => !t.Contains(o)), (t1, t2) => t1.Concat(new T[] { t2 })); } 

Salida:

 {1,2} {1,3} {1,4} {2,1} {2,3} {2,4} {3,1} {3,2} {3,4} {4,1} {4,2} {4,3} 

K-combinaciones con repetición

 static IEnumerable> GetKCombsWithRept(IEnumerable list, int length) where T : IComparable { if (length == 1) return list.Select(t => new T[] { t }); return GetKCombsWithRept(list, length - 1) .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) >= 0), (t1, t2) => t1.Concat(new T[] { t2 })); } 

Salida:

 {1,1} {1,2} {1,3} {1,4} {2,2} {2,3} {2,4} {3,3} {3,4} {4,4} 

K-combinaciones

 static IEnumerable> GetKCombs(IEnumerable list, int length) where T : IComparable { if (length == 1) return list.Select(t => new T[] { t }); return GetKCombs(list, length - 1) .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), (t1, t2) => t1.Concat(new T[] { t2 })); } 

Salida:

 {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} 

Eso se llama permutaciones.

Esto puede darle las permutaciones de cualquier colección:

 public class Permutation { public static IEnumerable GetPermutations(T[] items) { int[] work = new int[items.Length]; for (int i = 0; i < work.Length; i++) { work[i] = i; } foreach (int[] index in GetIntPermutations(work, 0, work.Length)) { T[] result = new T[index.Length]; for (int i = 0; i < index.Length; i++) result[i] = items[index[i]]; yield return result; } } public static IEnumerable GetIntPermutations(int[] index, int offset, int len) { if (len == 1) { yield return index; } else if (len == 2) { yield return index; Swap(index, offset, offset + 1); yield return index; Swap(index, offset, offset + 1); } else { foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) { yield return result; } for (int i = 1; i < len; i++) { Swap(index, offset, offset + i); foreach (int[] result in GetIntPermutations(index, offset + 1, len - 1)) { yield return result; } Swap(index, offset, offset + i); } } } private static void Swap(int[] index, int offset1, int offset2) { int temp = index[offset1]; index[offset1] = index[offset2]; index[offset2] = temp; } } 

Ejemplo:

 string[] items = { "one", "two", "three" }; foreach (string[] permutation in Permutation.GetPermutations(items)) { Console.WriteLine(String.Join(", ", permutation)); } 

Con respecto a la respuesta de Pengyang: Aquí está mi función genérica que puede devolver todas las combinaciones de una lista de T:

 static IEnumerable> GetCombinations(IEnumerable list, int length) { if (length == 1) return list.Select(t => new T[] { t }); return GetCombinations(list, length - 1) .SelectMany(t => list, (t1, t2) => t1.Concat(new T[] { t2 })); } 

Ejemplo 1: n = 3, k = 2

 IEnumerable> result = GetCombinations(Enumerable.Range(1, 3), 2); 

Salida – una lista de listas enteras:

 {1, 1} {1, 2} {1, 3} {2, 1} {2, 2} {2, 3} {3, 1} {3, 2} {3, 3} 

………………………………………….. ………………………

Ejecuté este ejemplo y no estoy seguro de la corrección de los resultados.

Ejemplo 2: n = 3, k = 3

 IEnumerable> result = GetCombinations(Enumerable.Range(1, 3), 3); 

Salida – una lista de listas enteras:

 {1, 1, 1} {1, 1, 2} {1, 1, 3} {1, 2, 1} {1, 2, 2} {1, 2, 3} {1, 3, 1} {1, 3, 2} {1, 3, 3} {2, 1, 1} {2, 1, 2} {2, 1, 3} {2, 2, 1} {2, 2, 2} {2, 2, 3} {2, 3, 1} {2, 3, 2} {2, 3, 3} {3, 1, 1} {3, 1, 2} {3, 1, 3} {3, 2, 1} {3, 2, 2} {3, 2, 3} {3, 3, 1} {3, 3, 2} {3, 3, 3} 

Esto no debería suceder con las combinaciones, de lo contrario debería especificar que es con la repetición.Ver el artículo http://en.wikipedia.org/wiki/Combinations

Quizás los kwcombinatorics pueden proporcionar cierta ayuda (ver ejemplo en la página de inicio):

La biblioteca de KwCombinatorics consta de 3 clases que brindan 3 formas diferentes de generar listas ordenadas (clasificadas) de combinaciones de números. Estos combinatorios son útiles para las pruebas de software, lo que permite la generación de varios tipos de posibles combinaciones de entrada. Otros usos incluyen resolver problemas matemáticos y juegos de azar.

Hay parejas de manera muy fácil de encontrar la combinación de entrada de cuerda por usuario.

Primera forma mediante el uso de LINQ

 private static IEnumerable FindPermutations(string set) { var output = new List(); switch (set.Length) { case 1: output.Add(set); break; default: output.AddRange(from c in set let tail = set.Remove(set.IndexOf(c), 1) from tailPerms in FindPermutations(tail) select c + tailPerms); break; } return output; } 

Use esta función como

 Console.WriteLine("Enter a sting "); var input = Console.ReadLine(); foreach (var stringCombination in FindPermutations(input)) { Console.WriteLine(stringCombination); } Console.ReadLine(); 

Otra forma es usar loop

 // 1. remove first char // 2. find permutations of the rest of chars // 3. Attach the first char to each of those permutations. // 3.1 for each permutation, move firstChar in all indexes to produce even more permutations. // 4. Return list of possible permutations. public static string[] FindPermutationsSet(string word) { if (word.Length == 2) { var c = word.ToCharArray(); var s = new string(new char[] { c[1], c[0] }); return new string[] { word, s }; } var result = new List(); var subsetPermutations = (string[])FindPermutationsSet(word.Substring(1)); var firstChar = word[0]; foreach (var temp in subsetPermutations.Select(s => firstChar.ToString() + s).Where(temp => temp != null).Where(temp => temp != null)) { result.Add(temp); var chars = temp.ToCharArray(); for (var i = 0; i < temp.Length - 1; i++) { var t = chars[i]; chars[i] = chars[i + 1]; chars[i + 1] = t; var s2 = new string(chars); result.Add(s2); } } return result.ToArray(); } 

puedes usar esta función como

 Console.WriteLine("Enter a sting "); var input = Console.ReadLine(); Console.WriteLine("Here is all the possable combination "); foreach (var stringCombination in FindPermutationsSet(input)) { Console.WriteLine(stringCombination); } Console.ReadLine(); 

Para una respuesta detallada, vea: Donald Knuth, The Art of computer programming (aka TAOCP). Volumen 4A, enumeración y retroceso, capítulo 7.2. Generando todas las posibilidades http://www-cs-faculty.stanford.edu/~uno/taocp.html

Otra versión de la solución dada por Gufa. Debajo del código fuente completo de la clase:

 using System.Collections.Generic; namespace ConsoleApplication1 { public class Permutation { public IEnumerable GetPermutations(T[] items) { var work = new int[items.Length]; for (var i = 0; i < work.Length; i++) { work[i] = i; } foreach (var index in GetIntPermutations(work, 0, work.Length)) { var result = new T[index.Length]; for (var i = 0; i < index.Length; i++) result[i] = items[index[i]]; yield return result; } } public IEnumerable GetIntPermutations(int[] index, int offset, int len) { switch (len) { case 1: yield return index; break; case 2: yield return index; Swap(index, offset, offset + 1); yield return index; Swap(index, offset, offset + 1); break; default: foreach (var result in GetIntPermutations(index, offset + 1, len - 1)) { yield return result; } for (var i = 1; i < len; i++) { Swap(index, offset, offset + i); foreach (var result in GetIntPermutations(index, offset + 1, len - 1)) { yield return result; } Swap(index, offset, offset + i); } break; } } private static void Swap(IList index, int offset1, int offset2) { var temp = index[offset1]; index[offset1] = index[offset2]; index[offset2] = temp; } } } 

Esto realmente funcionó como debería para combinaciones. Pero no permite elegir combinaciones de n en k …

Creé un método para obtener la combinación única de todos los elementos enteros en una matriz como se muestra a continuación. He usado Tuple para representar un par o una combinación de números:

 private static void CombinationsOfItemsInAnArray() { int[] arr = { 10, 50, 3, 1, 2 }; //unique elements var numberSet = new HashSet(); var combinationList = new List>(); foreach (var number in arr) { if (!numberSet.Contains(number)) { //create all tuple combinations for the current number against all the existing number in the number set foreach (var item in numberSet) combinationList.Add(new Tuple(number, item)); numberSet.Add(number); } } foreach (var item in combinationList) { Console.WriteLine("{{{0}}} - {{{1}}}",item.Item1,item.Item2); } } 

Cuando invoco este método en una aplicación de consola, obtengo el siguiente resultado:

 {50} - {10} {3} - {10} {3} - {50} {1} - {10} {1} - {50} {1} - {3} {2} - {10} {2} - {50} {2} - {3} {2} - {1}