Qual é a melhor maneira de encontrar todas as combinações de itens em uma matriz?

Qual é a melhor maneira de encontrar todas as combinações de itens em uma matriz em c #?

É O (n!)

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

ATUALIZADA

Aqui está um conjunto de funções genéricas (requerem .net 3.5 ou superior) para diferentes cenários. As saídas são para uma lista de {1, 2, 3, 4} e um comprimento de 2.

Permutações com repetição

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

Saída:

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

Permutações

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

Saída:

 {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-combinações com repetição

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

Saída:

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

Combinações K

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

Saída:

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

Isso é chamado de permutações.

Isso pode lhe dar as permutações de qualquer coleção:

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

Exemplo:

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

Em relação à resposta de Pengyang: Aqui está minha function genérica que pode retornar todas as combinações de uma 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 })); } 

Exemplo 1: n = 3, k = 2

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

Saída – uma lista de listas inteiras:

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

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

Eu corri este exemplo e não tenho certeza sobre o acerto dos resultados.

Exemplo 2: n = 3, k = 3

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

Saída – uma lista de listas inteiras:

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

Isso não deve acontecer com combinações, caso contrário, deve ser especificado com repetição. Consulte o artigo http://en.wikipedia.org/wiki/Combinations

Talvez o kwcombinatorics possa fornecer alguma assistência (veja o exemplo na página inicial):

A biblioteca KwCombinatorics são 3 classs que fornecem 3 maneiras diferentes de gerar listas ordenadas (classificadas) de combinações de números. Estas combinatórias são úteis para testes de software, permitindo a geração de vários tipos de combinações possíveis de input. Outros usos incluem a solução de problemas matemáticos e jogos de azar.

Há casais de maneira muito fácil de encontrar a combinação de input de string pelo usuário.

Primeira maneira usando o 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 function como

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

Outra maneira é usar o 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(); } 

você pode usar essa function 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 obter uma resposta detalhada, consulte: Donald Knuth, The Art of Computer Programming (também conhecido como TAOCP). Volume 4A, Enumeração e Backtracking, capítulo 7.2. Gerando todas as possibilidades. http://www-cs-faculty.stanford.edu/~uno/taocp.html

Outra versão da solução dada pela Gufa. Abaixo do código fonte completo da class:

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

Isso realmente funcionou como deveria para combinações.Mas é não permite escolher combinações de n em k …

Eu criei um método para obter a combinação exclusiva de todos os elementos inteiros em uma matriz, conforme mostrado abaixo. Eu usei Tuple para representar um par ou combinação 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); } } 

Quando invoco esse método em um aplicativo de console, obtenho a saída abaixo:

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