Générer toutes les combinaisons possibles

Sûr d'une chose. C'est un peu difficile à faire avec LINQ mais certainement possible en utilisant uniquement les opérateurs de requête standard.

Mise à jour: 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 y a 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 est de faire le produit cartésien de plusieurs séquences arbitrairement. "Zipping" dans les lettres est négligeable 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 ils sont combinés ensemble prend un certain temps pour s'y habituer:

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, commencez par comprendre ce que fait l'opération" accumulate". L'opération d'accumulation la plus simple est "ajouter tout dans cette séquence ensemble". La façon dont vous le faites est: commencez par zéro. Pour chaque élément de la séquence, la valeur actuelle de l'accumulateur est égal à la somme de l'élément et la valeur précédente de l'accumulateur. Nous faisons la même chose, sauf qu'au lieu d'accumuler la somme basée sur la somme jusqu'à présent et l'article 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 à plusieurs reprises le produit cartésien de l'accumulateur avec le suivant dans 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ésultats des opérateurs de séquence qu'il contient. Ce n'est pas ce que l'accumulateur fait contient. Ce que l'accumulateur contient réellement, ce sont les opérateurs qui produisent ces résultats. Ensemble l'opération ici construit juste un arbre massif 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é tant que la requête n'est pas exécutée. à des fins d'illustration, je vais montrer ce que lesRésultats sont à chaque étape du chemin, mais rappelez-vous, cela contient en fait les opérateurs qui produisent ces résultats.

Supposons que nous prenons le produit Cartésien de la séquence de les séquences {{1, 2}, {3, 4}, {5, 6}}. L'accumulateur commence comme une séquence contenant une séquence vide: { { } }

Sur la première accumulation, l'accumulateur est { { } } et de l'élément de {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 les avons réunis: Nous avons la paire ({ }, 1), nous avons donc concaténer { } et {1} pour obtenir {1}. Nous avons la paire ({ }, 2}), nous avons donc concaténer { } et {2} pour obtenir {2}. Par conséquent, nous avons {{1}, {2}} comme résultat.

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

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

Et puis à partir de ces éléments, concaténez le second sur le premier. Donc le résultat est la séquence {{1, 3}, {1, 4}, {2, 3}, {2, 4}}, qui 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), ...

, puis concaténer le deuxième élément sur le premier obtenir:

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

Et c'est fini. Nous avons accumulé le produit cartésien.

Maintenant que nous avons une fonction utilitaire qui peut prendre le produit cartésien de plusieurs séquences arbitrairement, le reste 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 de caractères par ligne:

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

Facile comme bonjour!

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 qui génère la langue souhaitée. 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

Il est clair que vous pouvez facilement générer cette chaîne de définition de grammaire à partir de vos deux tableaux. Puis alimentez cela dans le code qui génère toutes les chaînes dans une grammaire, et vous avez fait; vous aurez toutes les possibilités. (Pas necessesarily dans l'ordre que vous voulez dans, vous l'esprit.)

A titre de comparaison, voici un moyen 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)

Fon une autre solution non basée sur linq, 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.

Je ne suis pas prêt à vous donner le code source complet. Donc voilà l'idée derrière.

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

Je suppose A=(a1, a2, ..., an) et B=(b1, b2, ..., bn) (donc A et B chaque maintenez - n éléments).

Alors faites-le récursivement! Ecrire une méthode qui prend un A et un B et fait vos trucs:

Si A et B, chaque contenir qu'un seul élément (appelé an resp. bn), juste itération de 1 à bn et concaténer an à votre l'itération de la variable.

Si A et B contiennent chacun plus d'un élément, saisissez les premiers éléments (a1 resp b1), itérez de 1 à bn et faites pour chaque étape d'itération:

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

Ici Vous pouvez trouver un exemple analouge de la façon de générer des choses en C#, vous devez "juste" l'adapter à vos besoins.

Si je suis de bonne, vous êtes après quelque chose comme produit Cartésien. Si tel est le cas, voici comment vous pouvez le faire en utilisant LINQ. Peut-être pas la réponse exacte, mais essayez d'avoir 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 aider

• SelectMany

• Comment Utiliser LINQ SelectMany

Le résultat final est le tableau souhaité. Supposé que les deux tableaux sont de même taille.

char[] Array1 = { 'a', 'b', 'c' };
int[] Array2 = { 3, 2, 4 };

var finalResult = new List<string>();
finalResult.Add(String.Empty);
for(int i=0; i<Array1.Length; i++)
{
    var tmp = from a in finalResult
              from b in Enumerable.Range(1,Array2[i])
              select String.Format("{0} {1}{2}",a,Array1[i],b).Trim();
    finalResult = tmp.ToList();
}

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_string, collect) {
        if (temp_string.length) {
           collect.push(temp_string);
        }

        for (var i=0; i<arr.length; i++) {
            var arrcopy = arr.slice(0, arr.length);
            var elem = arrcopy.splice(i, 1);

            if (arrcopy.length > 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);

Je viens de découvrir cette publication CodeProject qui inclut une facette.Espace de noms combinatoire contenant du code utile pour gérer les Permuations, les combinaisons et les Variations en C#.

Http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G

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

static IEnumerable<T[]> CartesianProduct<T>(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]++;
        }
    }
}