Todas las combinaciones posibles de una lista de valores

Tengo una lista de enteros en mi progtwig C #. Sin embargo, sé la cantidad de elementos que tengo en mi lista solo en tiempo de ejecución.

Digamos, por simplicidad, mi lista es {1, 2, 3}. Ahora necesito generar todas las combinaciones posibles de la siguiente manera. {1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3}

¿Alguien puede ayudar con esto?

prueba esto:

static void Main(string[] args) { GetCombination(new List { 1, 2, 3 }); } static void GetCombination(List list) { double count = Math.Pow(2, list.Count); for (int i = 1; i < = count - 1; i++) { string str = Convert.ToString(i, 2).PadLeft(list.Count, '0'); for (int j = 0; j < str.Length; j++) { if (str[j] == '1') { Console.Write(list[j]); } } Console.WriteLine(); } } 

Aquí hay dos soluciones genéricas para listas fuertemente tipadas que devolverán todas las combinaciones únicas de miembros de la lista (si puede resolver esto con un código más simple, lo saludo):

 // Recursive public static List> GetAllCombos(List list) { List> result = new List>(); // head result.Add(new List()); result.Last().Add(list[0]); if (list.Count == 1) return result; // tail List> tailCombos = GetAllCombos(list.Skip(1).ToList()); tailCombos.ForEach(combo => { result.Add(new List(combo)); combo.Add(list[0]); result.Add(new List(combo)); }); return result; } // Iterative, using 'i' as bitmask to choose each combo members public static List> GetAllCombos(List list) { int comboCount = (int) Math.Pow(2, list.Count) - 1; List> result = new List>(); for (int i = 1; i < comboCount + 1; i++) { // make each combo here result.Add(new List()); for (int j = 0; j < list.Count; j++) { if ((i >> j) % 2 != 0) result.Last().Add(list[j]); } } return result; } // Example usage List> combos = GetAllCombos(new int[] { 1, 2, 3 }.ToList()); 

Aquí hay una solución genérica usando recursión

 public static ICollection> Permutations(ICollection list) { var result = new List>(); if (list.Count == 1) { // If only one possible permutation result.Add(list); // Add it and return it return result; } foreach (var element in list) { // For each element in that list var remainingList = new List(list); remainingList.Remove(element); // Get a list containing everything except of chosen element foreach (var permutation in Permutations(remainingList)) { // Get all possible sub-permutations permutation.Add(element); // Add that element result.Add(permutation); } } return result; } 

Sé que esta es una publicación anterior, pero a alguien le puede resultar útil.

Esta respuesta usa el mismo algoritmo que ojlovecd y (para su solución iterativa) jaolho. Lo único que agrego es una opción para filtrar los resultados para un número mínimo de elementos en las combinaciones. Esto puede ser útil, por ejemplo, si solo está interesado en las combinaciones que contienen al menos dos elementos.

Editar: según lo solicitado por @ user3610374, se agregó un filtro para la cantidad máxima de elementos.

Edición 2: como lo sugirió @stannius, el algoritmo se ha modificado para hacerlo más eficiente en los casos en que no se desean todas las combinaciones.

  ///  /// Method to create lists containing possible combinations of an input list of items. This is /// basically copied from code by user "jaolho" on this thread: /// http://stackoverflow.com/questions/7802822/all-possible-combinations-of-a-list-of-values ///  /// type of the items on the input list /// list of items /// minimum number of items wanted in the generated combinations, /// if zero the empty combination is included, /// default is one /// maximum number of items wanted in the generated combinations, /// default is no maximum limit /// list of lists for possible combinations of the input items public static List> ItemCombinations(List inputList, int minimumItems = 1, int maximumItems = int.MaxValue) { int nonEmptyCombinations = (int)Math.Pow(2, inputList.Count) - 1; List> listOfLists = new List>(nonEmptyCombinations + 1); // Optimize generation of empty combination, if empty combination is wanted if (minimumItems == 0) listOfLists.Add(new List()); if (minimumItems < = 1 && maximumItems >= inputList.Count) { // Simple case, generate all possible non-empty combinations for (int bitPattern = 1; bitPattern < = nonEmptyCombinations; bitPattern++) listOfLists.Add(GenerateCombination(inputList, bitPattern)); } else { // Not-so-simple case, avoid generating the unwanted combinations for (int bitPattern = 1; bitPattern <= nonEmptyCombinations; bitPattern++) { int bitCount = CountBits(bitPattern); if (bitCount >= minimumItems && bitCount < = maximumItems) listOfLists.Add(GenerateCombination(inputList, bitPattern)); } } return listOfLists; } ///  /// Sub-method of ItemCombinations() method to generate a combination based on a bit pattern. ///  private static List GenerateCombination(List inputList, int bitPattern) { List thisCombination = new List(inputList.Count); for (int j = 0; j < inputList.Count; j++) { if ((bitPattern >> j & 1) == 1) thisCombination.Add(inputList[j]); } return thisCombination; } ///  /// Sub-method of ItemCombinations() method to count the bits in a bit pattern. Based on this: /// https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan ///  private static int CountBits(int bitPattern) { int numberBits = 0; while (bitPattern != 0) { numberBits++; bitPattern &= bitPattern - 1; } return numberBits; } 

Otra solución usando Linq y recursión …

 static void Main(string[] args) { List> result = new List>(); List set = new List() { 1, 2, 3, 4 }; GetCombination(set, result); result.Add(set); IOrderedEnumerable> sorted = result.OrderByDescending(s => s.Count); sorted.ToList().ForEach(l => { l.ForEach(l1 => Console.Write(l1 + " ")); Console.WriteLine(); }); } private static void GetCombination(List set, List> result) { for (int i = 0; i < set.Count; i++) { List temp = new List(set.Where((s, index) => index != i)); if (temp.Count > 0 && !result.Where(l => l.Count == temp.Count).Any(l => l.SequenceEqual(temp))) { result.Add(temp); GetCombination(temp, result); } } } 

En primer lugar, dado un conjunto de n elementos, se calculan todas las combinaciones de k elementos (nCk). Debe cambiar el valor de k de 1 a n para cumplir con su requisito.

Vea este artículo del proyecto de código para el código C # para generar combinaciones.

En caso de que esté interesado en desarrollar el algoritmo de combinación usted mismo, consulte esta pregunta SO en la que hay muchos enlaces al material relevante.

Podemos usar recursión para problemas de combinación / permutación que involucren cadenas o enteros.

 public static void Main(string[] args) { IntegerList = new List { 1, 2, 3, 4 }; PrintAllCombination(default(int), default(int)); } public static List IntegerList { get; set; } public static int Length { get { return IntegerList.Count; } } public static void PrintAllCombination(int position, int prefix) { for (int i = position; i < Length; i++) { Console.WriteLine(prefix * 10 + IntegerList[i]); PrintAllCombination(i + 1, prefix * 10 + IntegerList[i]); } } 
 protected List> AllCombos(Func, List, bool> comparer, params T[] items) { List> results = new List>(); List workingWith = items.ToList(); results.Add(workingWith); items.ToList().ForEach((x) => { results.Add(new List() { x }); }); for (int i = 0; i < workingWith.Count(); i++) { T removed = workingWith[i]; workingWith.RemoveAt(i); List> nextResults = AllCombos2(comparer, workingWith.ToArray()); results.AddRange(nextResults); workingWith.Insert(i, removed); } results = results.Where(x => x.Count > 0).ToList(); for (int i = 0; i < results.Count; i++) { List list = results[i]; if (results.Where(x => comparer(x, list)).Count() > 1) { results.RemoveAt(i); } } return results; } protected List> AllCombos2(Func, List, bool> comparer, params T[] items) { List> results = new List>(); List workingWith = items.ToList(); if (workingWith.Count > 1) { results.Add(workingWith); } for (int i = 0; i < workingWith.Count(); i++) { T removed = workingWith[i]; workingWith.RemoveAt(i); List> nextResults = AllCombos2(comparer, workingWith.ToArray()); results.AddRange(nextResults); workingWith.Insert(i, removed); } results = results.Where(x => x.Count > 0).ToList(); for (int i = 0; i < results.Count; i++) { List list = results[i]; if (results.Where(x => comparer(x, list)).Count() > 1) { results.RemoveAt(i); } } return results; } 

Esto funcionó para mí, es un poco más complejo y en realidad toma una función de callback del comparador, y en realidad es de 2 funciones, con la diferencia de que AllCombos agrega las listas de elementos individuales explícitamente. Es muy crudo y definitivamente se puede recortar, pero hace el trabajo. Cualquier sugerencia de refactorización es bienvenida. Gracias,

 public class CombinationGenerator{ private readonly Dictionary currentIndexesWithLevels = new Dictionary(); private readonly LinkedList> _combinationsList = new LinkedList>(); private readonly int _combinationLength; public CombinationGenerator(int combinationLength) { _combinationLength = combinationLength; } private void InitializeLevelIndexes(List list) { for (int i = 0; i < _combinationLength; i++) { currentIndexesWithLevels.Add(i+1, i); } } private void UpdateCurrentIndexesForLevels(int level) { int index; if (level == 1) { index = currentIndexesWithLevels[level]; for (int i = level; i < _combinationLength + 1; i++) { index = index + 1; currentIndexesWithLevels[i] = index; } } else { int previousLevelIndex; for (int i = level; i < _combinationLength + 1; i++) { if (i > level) { previousLevelIndex = currentIndexesWithLevels[i - 1]; currentIndexesWithLevels[i] = previousLevelIndex + 1; } else { index = currentIndexesWithLevels[level]; currentIndexesWithLevels[i] = index + 1; } } } } public void FindCombinations(List list, int level, Stack stack) { int currentIndex; InitializeLevelIndexes(list); while (true) { currentIndex = currentIndexesWithLevels[level]; bool levelUp = false; for (int i = currentIndex; i < list.Count; i++) { if (level < _combinationLength) { currentIndex = currentIndexesWithLevels[level]; MoveToUpperLevel(ref level, stack, list, currentIndex); levelUp = true; break; } levelUp = false; stack.Push(list[i]); if (stack.Count == _combinationLength) { AddCombination(stack); stack.Pop(); } } if (!levelUp) { MoveToLowerLevel(ref level, stack, list, ref currentIndex); while (currentIndex >= list.Count - 1) { if (level == 1) { AdjustStackCountToCurrentLevel(stack, level); currentIndex = currentIndexesWithLevels[level]; if (currentIndex >= list.Count - 1) { return; } UpdateCurrentIndexesForLevels(level); } else { MoveToLowerLevel(ref level, stack, list, ref currentIndex); } } } } } private void AddCombination(Stack stack) { List listNew = new List(); listNew.AddRange(stack); _combinationsList.AddLast(listNew); } private void MoveToUpperLevel(ref int level, Stack stack, List list, int index) { stack.Push(list[index]); level++; } private void MoveToLowerLevel(ref int level, Stack stack, List list, ref int currentIndex) { if (level != 1) { level--; } AdjustStackCountToCurrentLevel(stack, level); UpdateCurrentIndexesForLevels(level); currentIndex = currentIndexesWithLevels[level]; } private void AdjustStackCountToCurrentLevel(Stack stack, int currentLevel) { while (stack.Count >= currentLevel) { if (stack.Count != 0) stack.Pop(); } } public void PrintPermutations() { int count = _combinationsList.Where(perm => perm.Count() == _combinationLength).Count(); Console.WriteLine("The number of combinations is " + count); } } 

Qué pasa

 static void Main(string[] args) { Combos(new [] { 1, 2, 3 }); } static void Combos(int[] arr) { for (var i = 0; i < = Math.Pow(2, arr.Length); i++) { Console.WriteLine(); var j = i; var idx = 0; do { if ((j & 1) == 1) Console.Write($"{arr[idx]} "); } while ((j >>= 1) > 0 && ++idx < arr.Length); } } 

Una versión un poco más generalizada para Linq usando C # 7. Aquí se filtra por elementos que tienen dos elementos.

 static void Main(string[] args) { foreach (var vals in Combos(new[] { "0", "1", "2", "3" }).Where(v => v.Skip(1).Any() && !v.Skip(2).Any())) Console.WriteLine(string.Join(", ", vals)); } static IEnumerable> Combos(T[] arr) { IEnumerable DoQuery(long j, long idx) { do { if ((j & 1) == 1) yield return arr[idx]; } while ((j >>= 1) > 0 && ++idx < arr.Length); } for (var i = 0; i < Math.Pow(2, arr.Length); i++) yield return DoQuery(i, 0); }