Gerando todas as combinações possíveis

Dado 2 arrays Array1 = {a,b,c...n} e Array2 = {10,20,15....x} como posso gerar todas as combinações possíveis como Strings a (i) b (j) c ( k) n (p) onde

 1 <= i <= 10, 1 <= j <= 20 , 1 <= k <= 15, .... 1 <= p <= x 

Tal como:

 a1 b1 c1 .... n1 a1 b1 c1..... n2 ...... ...... a10 b20 c15 nx (last combination) 

Assim, em todo o número total de combinação = produto de elementos da array2 = (10 X 20 X 15 X ..X x)

Semelhante a um produto cartesiano, no qual a segunda matriz define o limite superior para cada elemento na primeira matriz.

Exemplo com números fixos

  Array x = [a,b,c] Array y = [3,2,4] 

Então teremos 3 * 2 * 4 = 24 combinações. Os resultados devem ser:

  a1 b1 c1 a1 b1 c2 a1 b1 c3 a1 b1 c4 a1 b2 c1 a1 b2 c2 a1 b2 c3 a1 b2 c4 a2 b1 c1 a2 b1 c2 a2 b1 c3 a2 b1 c4 a2 b2 c1 a2 b2 c2 a2 b2 c3 a2 b2 c4 a3 b1 c1 a3 b1 c2 a3 b1 c3 a3 b1 c4 a3 b2 c1 a3 b2 c2 a3 b2 c3 a3 b2 c4 (last) 

 using System; using System.Text; public static string[] GenerateCombinations(string[] Array1, int[] Array2) { if(Array1 == null) throw new ArgumentNullException("Array1"); if(Array2 == null) throw new ArgumentNullException("Array2"); if(Array1.Length != Array2.Length) throw new ArgumentException("Must be the same size as Array1.", "Array2"); if(Array1.Length == 0) return new string[0]; int outputSize = 1; var current = new int[Array1.Length]; for(int i = 0; i < current.Length; ++i) { if(Array2[i] < 1) throw new ArgumentException("Contains invalid values.", "Array2"); if(Array1[i] == null) throw new ArgumentException("Contains null values.", "Array1"); outputSize *= Array2[i]; current[i] = 1; } var result = new string[outputSize]; for(int i = 0; i < outputSize; ++i) { var sb = new StringBuilder(); for(int j = 0; j < current.Length; ++j) { sb.Append(Array1[j]); sb.Append(current[j].ToString()); if(j != current.Length - 1) sb.Append(' '); } result[i] = sb.ToString(); int incrementIndex = current.Length - 1; while(incrementIndex >= 0 && current[incrementIndex] == Array2[incrementIndex]) { current[incrementIndex] = 1; --incrementIndex; } if(incrementIndex >= 0) ++current[incrementIndex]; } return result; } 

Coisa certa. É um pouco difícil fazer isso com o LINQ, mas certamente é possível usando apenas os operadores de consulta padrão.

ATUALIZAÇÃO: Este é o assunto do meu blog na segunda-feira 28 de junho de 2010 ; Obrigado pela ótima pergunta. Além disso, um comentarista no meu blog observou que há uma consulta ainda mais elegante do que a que eu dei. Vou atualizar o código aqui para usá-lo.

A parte complicada é fazer o produto cartesiano de arbitrariamente muitas seqüências. “Zipping” nas letras é trivial comparado a isso. Você deve estudar isso para se certificar de que entende como funciona. Cada parte é simples o suficiente, mas a maneira como elas são combinadas leva algum tempo para se acostumar:

 static IEnumerable> CartesianProduct(this IEnumerable> sequences) { IEnumerable> emptyProduct = new[] { Enumerable.Empty()}; return sequences.Aggregate( emptyProduct, (accumulator, sequence) => from accseq in accumulator from item in sequence select accseq.Concat(new[] {item}) ); } 

Para explicar como isso funciona, primeiro entenda o que a operação “acumular” está fazendo. A operação de acumulação mais simples é “some tudo nesta seqüência juntos”. A maneira de fazer isso é: começar com zero. Para cada item na sequência, o valor atual do acumulador é igual à sum do item e do valor anterior do acumulador. Estamos fazendo a mesma coisa, exceto que, em vez de acumular a sum com base na sum até o momento e no item atual, estamos acumulando o produto cartesiano à medida que avançamos.

A maneira como vamos fazer isso é aproveitar o fato de que já temos um operador no LINQ que calcula o produto cartesiano de duas coisas:

 from x in xs from y in ys do something with each possible (x, y) 

Tomando repetidamente o produto cartesiano do acumulador com o próximo item na sequência de input e fazendo um pequeno agrupamento dos resultados, podemos gerar o produto cartesiano à medida que avançamos.

Então pense no valor do acumulador. Para fins ilustrativos, mostrarei o valor do acumulador como os resultados dos operadores de sequência que ele contém. Isso não é o que o acumulador realmente contém. O que o acumulador realmente contém são os operadores que produzem esses resultados. Toda a operação aqui apenas constrói uma tree maciça de operadores de sequência, cujo resultado é o produto cartesiano. Mas o produto cartesiano final em si não é realmente computado até que a consulta seja executada. Para fins ilustrativos, mostrarei quais são os resultados em cada estágio do caminho, mas lembre-se de que isso realmente contém os operadores que produzem esses resultados.

Suponha que estamos tomando o produto cartesiano da seqüência de seqüências {{1, 2}, {3, 4}, {5, 6}} . O acumulador começa como uma sequência contendo uma sequência vazia: { { } }

Na primeira acumulação, o acumulador é {{}} e o item é {1, 2}. Nós fazemos isso:

 from accseq in accumulator from item in sequence select accseq.Concat(new[] {item}) 

Então, estamos levando o produto cartesiano de { { } } com {1, 2} e, para cada par, concatenamos: temos o par ({ }, 1) , então concatenamos { } e {1} para obter {1} . Nós temos o par ({ }, 2}) , então nós concatenamos { } e {2} para obter {2} . Portanto, temos {{1}, {2}} como resultado.

Então, no segundo acúmulo, o acumulador é {{1}, {2}} e o item é {3, 4} . Mais uma vez, calculamos o produto cartesiano dessas duas seqüências para obter:

  {({1}, 3), ({1}, 4), ({2}, 3), ({2}, 4)} 

e depois desses itens, concatene o segundo no primeiro. Então o resultado é a sequência {{1, 3}, {1, 4}, {2, 3}, {2, 4}} , que é o que queremos.

Agora nos acumulamos novamente. Pegamos o produto cartesiano do acumulador com {5, 6} para obter

  {({ 1, 3}, 5), ({1, 3}, 6), ({1, 4}, 5), ... 

e concatenar o segundo item no primeiro para obter:

 {{1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6} ... } 

e terminamos Nós acumulamos o produto cartesiano.

Agora que temos uma function de utilidade que pode levar arbitrariamente ao produto cartesiano muitas seqüências, o resto é fácil por comparação:

 var arr1 = new[] {"a", "b", "c"}; var arr2 = new[] { 3, 2, 4 }; var result = from cpLine in CartesianProduct( from count in arr2 select Enumerable.Range(1, count)) select cpLine.Zip(arr1, (x1, x2) => x2 + x1); 

E agora nós temos uma seqüência de seqüências de strings, uma seqüência de strings por linha:

 foreach (var line in result) { foreach (var s in line) Console.Write(s); Console.WriteLine(); } 

Mole-mole!

Solução alternativa:

Etapa 1: leia minha série de artigos sobre como gerar todas as strings que correspondam a uma gramática sensível ao contexto:

http://blogs.msdn.com/b/ericlippert/archive/tags/grammars/

Etapa dois: defina uma gramática que gere o idioma desejado. Por exemplo, você poderia definir a gramática:

 S: a A b B c C A: 1 | 2 | 3 B: 1 | 2 C: 1 | 2 | 3 | 4 

É claro que você pode gerar facilmente essa string de definição gramatical de seus dois arrays. Em seguida, insira isso no código que gera todas as strings em uma determinada gramática e pronto; você terá todas as possibilidades. (Não necessariamente na ordem em que você os quer entrar, lembre-se.)

Para comparação, aqui está uma maneira de fazer isso com o Python

 from itertools import product X=["a", "b", "c"] Y=[3, 4, 2] terms = (["%s%s"%(x,i+1) for i in range(y)] for x,y in zip(X,Y)) for item in product(*terms): print " ".join(item) 

Fon outra solução não baseada em linq você pode usar:

 public class CartesianProduct { int[] lengths; T[][] arrays; public CartesianProduct(params T[][] arrays) { lengths = arrays.Select(k => k.Length).ToArray(); if (lengths.Any(l => l == 0)) throw new ArgumentException("Zero lenght array unhandled."); this.arrays = arrays; } public IEnumerable Get() { int[] walk = new int[arrays.Length]; int x = 0; yield return walk.Select(k => arrays[x++][k]).ToArray(); while (Next(walk)) { x = 0; yield return walk.Select(k => arrays[x++][k]).ToArray(); } } private bool Next(int[] walk) { int whoIncrement = 0; while (whoIncrement < walk.Length) { if (walk[whoIncrement] < lengths[whoIncrement] - 1) { walk[whoIncrement]++; return true; } else { walk[whoIncrement] = 0; whoIncrement++; } } return false; } } 

Você pode encontrar um exemplo de como usá-lo aqui .

Eu não estou disposto a dar-lhe o código-fonte completo. Então aqui está a ideia por trás.

Você pode gerar os elementos da seguinte maneira:

Eu assumo A=(a1, a2, ..., an) e B=(b1, b2, ..., bn) (assim A e B cada um contém n elementos).

Então faça isso recursivamente! Escreva um método que tome um A e um B e faça suas coisas:

Se A e B contiverem apenas um elemento (chamado de resp. bn ), basta iterar de 1 para bn e concatenar an para sua variável de iteração.

Se A e B contiverem mais de um elemento, pegue os primeiros elementos ( a1 resp b1 ), itere de 1 a bn e faça por cada etapa de iteração:

  • chame o método recursivamente com os subcampos de A e B começando no segundo elemento, ie A'=(a2, a3, ..., an) resp B'=(b2, b3, ..., bn) . Para cada elemento gerado pela chamada recursiva, concatene a1 , a variável de iteração e o elemento gerado da chamada recursiva.

Aqui você pode encontrar um exemplo analógico de como gerar coisas em C #, você “apenas” tem que adaptá-lo às suas necessidades.

Se estou acertando, você está atrás de algo como um produto cartesiano . Se este for o caso, aqui está como você pode fazer isso usando o LINQ. Pode não ser uma resposta exata, mas tente entender


  char[] Array1 = { 'a', 'b', 'c' }; string[] Array2 = { "10", "20", "15" }; var result = from i in Array1 from j in Array2 select i + j; 

Estes artigos podem ajudar

  • SelecioneMuitos

  • Como usar o LINQ SelectMany

O finalResult é o array desejado. Assumindo que as duas matrizes são do mesmo tamanho.

 char[] Array1 = { 'a', 'b', 'c' }; int[] Array2 = { 3, 2, 4 }; var finalResult = new List(); finalResult.Add(String.Empty); for(int i=0; i 

Eu acho que isso será suficiente.

Aqui está uma versão de javascript, que tenho certeza que alguém pode converter. Foi testado minuciosamente.

Aqui está o violino .

 function combinations (Asource){ var combos = []; var temp = []; var picker = function (arr, temp_string, collect) { if (temp_string.length) { collect.push(temp_string); } for (var i=0; i 0) { picker(arrcopy, temp_string.concat(elem), collect); } else { collect.push(temp_string.concat(elem)); } } } picker(Asource, temp, combos); return combos; } var todo = ["a", "b", "c", "d"]; // 5 in this set var resultingCombos = combinations (todo); console.log(resultingCombos); 

Acabei de descobrir este lançamento do CodeProject que inclui um namespace Facets.Combinatorics contendo algum código útil para lidar com Permutas, Combinações e Variações em C #.

http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-CG

Outra solução não baseada em linq, mais efetiva:

 static IEnumerable CartesianProduct(T[][] arrays) { int[] lengths; lengths = arrays.Select(a => a.Length).ToArray(); int Len = arrays.Length; int[] inds = new int[Len]; int Len1 = Len - 1; while (inds[0] != lengths[0]) { T[] res = new T[Len]; for (int i = 0; i != Len; i++) { res[i] = arrays[i][inds[i]]; } yield return res; int j = Len1; inds[j]++; while (j > 0 && inds[j] == lengths[j]) { inds[j--] = 0; inds[j]++; } } }