Générer toutes les combinaisons possibles

Question

Étant donné 2 tableaux Array1 = {a,b,c...n} et Array2 = {10,20,15....x} Comment puis-je générer toutes les combinaisons possibles sous forme de chaînes de caractères ? a(i) b(j) c(k) n(p) où

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

Par exemple :

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

Donc en tout le nombre total de combinaison = produit des éléments de array2 = (10 X 20 X 15 X ..X x)

Similaire à un produit cartésien, dans lequel le second tableau définit la limite supérieure de chaque élément du premier tableau.

Exemple avec des nombres fixes,

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

Nous aurons donc 3*2*4 = 24 combinaisons. Les résultats devraient être :

    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)

Answer 1

Bien sûr. C'est un peu délicat de faire cela avec LINQ mais certainement possible en utilisant seulement les opérateurs de requête standard.

UPDATE : C'est le sujet de mon blog le lundi 28 juin 2010 Merci pour cette excellente question. Par ailleurs, un commentateur de mon blog a fait remarquer qu'il existe une requête encore plus élégante que celle que j'ai donnée. Je vais mettre à jour le code ici pour l'utiliser.

La partie délicate consiste à faire le produit cartésien d'un nombre arbitraire de séquences. "Zipper" les lettres est trivial comparé à cela. Vous devriez étudier ceci pour vous assurer que vous comprenez comment cela fonctionne. Chaque partie est assez simple, mais il faut s'habituer à la façon dont elles sont combinées :

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

Pour expliquer comment cela fonctionne, il faut d'abord comprendre ce que fait l'opération "accumuler". L'opération d'accumulation la plus simple consiste à "additionner tout ce qui se trouve dans cette séquence". Pour ce faire, il faut commencer par zéro. Pour chaque élément de la séquence, la valeur actuelle de l'accumulateur est égale à la somme 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 somme en fonction de la somme précédente et de l'élément actuel, nous accumulons le produit cartésien au fur et à mesure.

La façon dont nous allons le faire est de profiter 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 de manière répétée le produit cartésien de l'accumulateur avec l'élément suivant de la séquence d'entrée et en faisant un petit collage des résultats, nous pouvons générer le produit cartésien au fur et à mesure.

Pensez donc à la valeur de l'accumulateur. À des fins d'illustration, je vais montrer que la valeur de l'accumulateur est la suivante résultats des opérateurs de séquence qu'il contient. Ce n'est pas ce que l'accumulateur en fait contient. Ce que l'accumulateur contient réellement est le opérateurs qui produisent ces résultats. Toute l'opération ici ne fait qu'accumuler massif arbre d'opérateurs de séquence, dont le résultat est le produit cartésien. Mais le produit cartésien final lui-même n'est pas réellement calculé avant l'exécution de la requête. A titre d'illustration, je vais montrer ce que le résultats sont à chaque étape du parcours, mais n'oubliez pas qu'il s'agit en réalité de la 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 comme une séquence contenant une séquence vide : { { } }

Lors de la première accumulation, l'accumulateur est { { } } et l'élément est {1, 2}. On fait ça :

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

Donc nous prenons 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.

Donc, lors de la deuxième accumulation, l'accumulateur est {{1}, {2}} et l'article est {3, 4} . Encore une fois, on calcule le produit cartésien de ces deux séquences pour obtenir :

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

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

Maintenant, nous accumulons à nouveau. Nous prenons le produit cartésien de l'accumulateur avec {5, 6} pour obtenir

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

et ensuite concaténer le deuxième élément sur le premier pour obtenir :

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

et on a fini. Nous avons accumulé le produit cartésien.

Maintenant que nous avons une fonction d'utilité qui peut prendre le produit cartésien d'un nombre arbitraire de séquences, le reste est facile en 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 de caractères, une séquence de chaînes de caractères par ligne :

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

C'est facile !

Answer 2

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

Answer 3

Solution alternative :

Première étape : lisez ma série d'articles sur la façon de générer toutes les chaînes de caractères qui correspondent à une grammaire sensible au contexte :

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

Deuxième étape : définir une grammaire qui génère le langage que vous voulez. Par exemple, vous pourriez définir la grammaire :

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

Il est clair que vous pouvez facilement générer cette chaîne de définition de la grammaire à partir de vos deux tableaux. Ensuite, introduisez-la dans le code qui génère toutes les chaînes d'une grammaire donnée, et le tour est joué ; vous obtiendrez toutes les possibilités. (Pas nécessairement dans l'ordre où vous les voulez, remarquez).

Answer 4

Fon une autre solution non basée sur linq que vous pouvez utiliser :

public class CartesianProduct<T>
    {
        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<T[]> 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 sur comment l'utiliser ici .

Answer 5

Si j'ai bien compris, vous cherchez quelque chose du genre Produit cartésien . Si c'est le cas, voici comment vous pouvez le faire en utilisant LINQ. Ce n'est peut-être pas la réponse exacte, mais essayez de comprendre l'idée.

---

    char[] Array1 = { 'a', 'b', 'c' };
    string[] Array2 = { "10", "20", "15" };

    var result = from i in Array1
                 from j in Array2
                   select i + j;

---

Ces articles pourraient vous aider

• SelectMany

• Comment utiliser SelectMany de LINQ