Générer toutes les combinaisons possibles

 using System; using System.Text; public static ssortingng[] GenerateCombinations(ssortingng[] 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 ssortingng[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; } 

Chose sûre. C’est un peu délicat de faire cela avec LINQ mais cela est certainement possible en utilisant uniquement les opérateurs de requête standard.

UPDATE: C’est le sujet de mon blog du lundi 28 juin 2010 ; merci pour la grande question. En outre, un commentateur sur mon blog a noté qu’il existait une requête encore plus élégante que celle que j’avais donnée. Je vais mettre à jour le code ici pour l’utiliser.

La difficulté consiste à créer le produit cartésien de nombreuses séquences arbitrairement. “Zipping” dans les lettres est sortingvial par rapport à cela. Vous devriez étudier cela pour vous assurer que vous comprenez comment cela fonctionne. Chaque partie est assez simple, mais la façon dont elles sont combinées demande de l’habitude:

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

Pour expliquer comment cela fonctionne, commencez par comprendre ce que fait l’opération “accumuler”. L’opération d’accumulation la plus simple est “tout append dans cette séquence ensemble”. Pour ce faire, procédez comme suit: commencez par zéro. Pour chaque élément de la séquence, la valeur actuelle de l’accumulateur est égale à la sum de l’élément et de la valeur précédente de l’accumulateur. Nous faisons la même chose, sauf qu’au lieu d’accumuler la sum en fonction de la sum obtenue jusqu’à présent et de l’élément en cours, nous accumulons le produit cartésien au fur et à mesure.

Pour ce faire, nous allons tirer parti du fait que nous avons déjà un opérateur dans LINQ qui calcule le produit cartésien de deux choses:

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

En prenant à plusieurs resockets le produit cartésien de l’accumulateur avec le prochain élément de la séquence d’entrée et en collant un peu les résultats, nous pouvons générer le produit cartésien au fur et à mesure.

Alors pensez à la valeur de l’accumulateur. À des fins d’illustration, je vais montrer la valeur de l’accumulateur en tant que résultat des opérateurs de séquence qu’il contient. Ce n’est pas ce que l’accumulateur contient réellement . Ce que l’accumulateur contient réellement, ce sont les opérateurs qui produisent ces résultats. L’ensemble de l’opération ici ne fait que constituer une énorme arborescence d’opérateurs de séquence, dont le résultat est le produit cartésien. Mais le produit cartésien final n’est pas réellement calculé tant que la requête n’est pas exécutée. À des fins d’illustration, je montrerai quels sont les résultats à chaque étape du processus, mais rappelez-vous que cela contient en fait les opérateurs qui produisent ces résultats.

Supposons que nous prenions le produit cartésien de la séquence de séquences {{1, 2}, {3, 4}, {5, 6}} . L’accumulateur commence par une séquence contenant une séquence vide: { { } }

Lors de la première accumulation, l’accumulateur est {{}} et l’élément est {1, 2}. Nous faisons ceci:

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

Nous prenons donc le produit cartésien de { { } } avec {1, 2} et pour chaque paire, nous concaténons: Nous avons la paire ({ }, 1) , donc nous concaténons { } et {1} pour obtenir {1} . Nous avons la paire ({ }, 2}) , donc nous concaténons { } et {2} pour obtenir {2} . Par conséquent, nous avons {{1}, {2}} comme résultat.

Ainsi, lors de la deuxième accumulation, l’accumulateur est {{1}, {2}} et l’élément est {3, 4} . De nouveau, nous calculons le produit cartésien de ces deux séquences pour obtenir:

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

puis à partir de ces éléments, concaténez le second sur le premier. Le résultat est donc la séquence {{1, 3}, {1, 4}, {2, 3}, {2, 4}} , ce que nous voulons.

Maintenant, nous accumulons à nouveau. On prend le produit cartésien de l’accumulateur avec {5, 6} pour obtenir

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

puis concaténez le deuxième élément sur le premier pour obtenir:

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

et nous avons fini. Nous avons accumulé le produit cartésien.

Maintenant que nous avons une fonction d’utilité qui peut prendre le produit cartésien de nombreuses séquences de manière arbitraire, le rest est facile par comparaison:

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

Et maintenant nous avons une séquence de séquences de chaînes, une séquence de chaînes par ligne:

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

Peasy facile!

Solution alternative:

Première étape: lisez ma série d’articles sur la façon de générer toutes les chaînes qui correspondent à une grammaire contextuelle:

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

Deuxième étape: définissez une grammaire générant le langage souhaité. Par exemple, vous pouvez définir la grammaire:

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

Clairement, vous pouvez facilement générer cette chaîne de définition de grammaire à partir de vos deux tableaux. Introduisez ensuite cela dans le code qui génère toutes les chaînes d’une grammaire donnée, et vous avez terminé. vous aurez toutes les possibilités. (Pas nécessairement dans l’ordre dans lequel vous les voulez, remarquez.)

Pour comparaison, voici une façon de le faire avec 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) 

Pour une autre solution non basée sur linq, vous pouvez utiliser:

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

Vous pouvez trouver un exemple d'utilisation ici .

Je ne suis pas disposé à vous donner le code source complet. Alors voici l’idée derrière.

Vous pouvez générer les éléments de la manière suivante:

Je suppose que A=(a1, a2, ..., an) et B=(b1, b2, ..., bn) (donc A et B contiennent chacun n éléments).

Alors fais-le récursivement! Ecrivez une méthode qui prend un A et un B et fait votre travail:

Si A et B contiennent chacun qu’un seul élément (appelé an resp. bn ), il suffit d’itérer de 1 à bn et de concaténer an à votre variable itérative.

Si A et B contiennent chacun plus d’un élément, saisissez les premiers éléments ( a1 ou b1 ), parcourez de 1 à bn et effectuez-les à chaque étape:

• appelez la méthode récursivement avec les sous-champs de A et B commençant au deuxième élément, c’est-à-dire A'=(a2, a3, ..., an) ou B'=(b2, b3, ..., bn) . Pour chaque élément généré par l’appel récursif, concaténez a1 , la variable itérative et l’élément généré à partir de l’appel récursif.

Ici vous pouvez trouver un exemple détaillé de la génération de choses en C #, il vous suffit de “l’adapter” à vos besoins.

Si je comprends bien, vous recherchez un produit cartésien . Si tel est le cas, voici comment vous pouvez le faire avec LINQ. Peut-être pas une réponse exacte mais essayez de vous faire une idée

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

Ces articles pourraient aider

• SelectMany

• Comment utiliser LINQ SelectMany

FinalResult est le tableau souhaité. Supposons que les deux tableaux ont la même taille.

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

Je pense que cela suffira.

Voici une version javascript, que je suis sûr que quelqu’un peut convertir. Il a été testé à fond.

Voici le violon .

 function combinations (Asource){ var combos = []; var temp = []; var picker = function (arr, temp_ssortingng, collect) { if (temp_ssortingng.length) { collect.push(temp_ssortingng); } for (var i=0; i 0) { picker(arrcopy, temp_ssortingng.concat(elem), collect); } else { collect.push(temp_ssortingng.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); 

Une autre solution non basée sur linq, plus efficace:

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

Je viens de découvrir cette publication CodeProject qui inclut un espace de noms Facets.Combinatorics contenant du code utile pour gérer les permutations, combinaisons et variations en C #.

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