Tutte le possibili combinazioni di un elenco di valori

Ho una lista di numeri interi nel mio programma C #. Tuttavia, conosco il numero di elementi che ho nella mia lista solo in fase di esecuzione.

Diciamo, per semplicità, la mia lista è {1, 2, 3} Ora ho bisogno di generare tutte le combinazioni possibili come segue. {1, 2, 3} {1, 2} {1, 3} {2, 3} {1} {2} {3}

Qualcuno può aiutare con questo?

prova questo:

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(); } } 

Ecco due soluzioni generiche per elenchi fortemente tipizzati che restituiranno tutte le combinazioni univoche dei membri della lista (se riesci a risolverlo con un codice più semplice, ti saluto):

 // 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()); 

Ecco una soluzione generica che utilizza la ricorsione

 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; } 

So che questo è un vecchio post, ma qualcuno potrebbe trovarlo utile.

Questa risposta utilizza lo stesso algoritmo di ojlovecd e (per la sua soluzione iterativa) jaolho. L’unica cosa che sto aggiungendo è un’opzione per filtrare i risultati per un numero minimo di elementi nelle combinazioni. Questo può essere utile, ad esempio, se sei interessato solo alle combinazioni che contengono almeno due elementi.

Modifica: come richiesto da @ user3610374 è stato aggiunto un filtro per il numero massimo di elementi.

Modifica 2: come suggerito da @stannius, l’algoritmo è stato modificato per renderlo più efficiente nei casi in cui non sono richieste tutte le combinazioni.

  ///  /// 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; } 

Un’altra soluzione che utilizza Linq e la ricorsione …

 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); } } } 

In primo luogo, dato un insieme di n elementi, si calcolano tutte le combinazioni di elementi k da esso (nCk). Devi cambiare il valore di k da 1 a n per soddisfare i tuoi requisiti.

Vedi questo articolo codeproject per il codice C # per generare combinazioni.

Nel caso in cui sei interessato a sviluppare da solo l’algoritmo di combinazione, controlla questa domanda SO dove ci sono molti link al materiale pertinente.

Possiamo usare la ricorsione per problemi di combinazione / permutazione che coinvolgono string o interi.

 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; } 

Questo ha funzionato per me, è leggermente più complesso e richiede effettivamente una funzione di callback comparativo, ed è in realtà 2 funzioni, con la differenza che AllCombos aggiunge esplicitamente gli elenchi di singoli elementi. È molto grezzo e può essere sradicato, ma ottiene il lavoro. Qualsiasi suggerimento per il refactoring è benvenuto. Grazie,

 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); } } 

Che dire

 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 versione leggermente più generalizzata per Linq usando C # 7. Qui si filtra per elementi che hanno due elementi.

 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); }