Rendre une méthode récursive avec Yield return

Version imprimable

Bonjour,

Voici 2 méthodes, le but est de "multiplier" une liste n fois. La première méthode multiplie 2 fois ma liste alors que l'autre méthode multiplie 3 fois la liste.
J'aimerai réussir à trouver une écriture permettant d'utiliser mon paramètre int aNombreCaractere afin d'avoir une seule méthode qui s'appelle récursivement n fois en fonction du paramètre ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
        public static System.Collections.IEnumerable MultiplyCaractere(int aNombreCaractere)
        {
            String locale = null;
 
            foreach (String item1 in GetAllCaractere())
            {
                foreach (String item2 in GetAllCaractere())
                {
                    locale = String.Format("{0}{1}", item1, item2);
                    yield return locale;
                }
            }
        }
 
        public static System.Collections.IEnumerable MultiplyCaractere3(int aNombreCaractere)
        {
            String locale = null;
 
            foreach (String item1 in GetAllCaractere())
            {
                foreach (String item2 in GetAllCaractere())
                {
                    foreach (String item3 in GetAllCaractere())
                    {
                        locale = item1 + item2 + item3;
                        yield return locale;
                    }
                }
            }
        }

À priori, ici c'est le yield return qui me pose problème, et je ne sais pas comment m'en sortir, si vous avez des idées ?

Merci beaucoup

18/04/2013, 11h58
k4st0r42

Ça risque d'être compliqué ce que tu veux faire avec un yield
18/04/2013, 12h04
Ticoche

Le yield n'est pas une obligation, cependant je l'utilise pour résoudre un problème technique, en effet, si je multiplie 4 ou 5 listes, j'ai +38.000.000 enregistrements, et cela ne tient pas dans une liste (exception) d'où le yield.
Maintenant s'il existe une autre solution pour parcourir tous mes enregistrements "à la volée" je suis preneur ^^

édit :
Exception of type 'System.OutOfMemoryException' was thrown.
lstTest2 Count = 33554432 System.Collections.Generic.List<string>
Donc après 33554432 enregistrements la liste lève une exception !
18/04/2013, 13h27
Bluedeep

Bonjour

Peux tu préciser l'usage de ton aNombreCaractere ? c'est le niveau de multiplication par lui même de ton tableau de caractère ?

Bonjour,

Le problème à résoudre est très intéressant ! :)

Voici ma solution avec Linq:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    class Program
    {
        private const string _allChars = "abcdefghijklmnopqrstuvwxyz";
 
        private static void Main(string[] args)
        {
            var list = MultiplyCaractere(10);
 
            foreach (var val in list)
            {
                Console.WriteLine(val);
            }
        }
 
        /// <summary>
        /// Récupérer les combinaison
        /// </summary>
        /// <param name="aNombreCaractere">Taille</param>
        /// <returns></returns>
        public static System.Collections.IEnumerable MultiplyCaractere(int aNombreCaractere)
        {
            IEnumerable<string> list = GetAllCaractere();
 
            for (var i = 1; i < aNombreCaractere; i++)
            {
                list = from l in list from n in GetAllCaractere() select  l + n;
            }
 
            return list;
        }
 
        /// <summary>
        /// Récupérer une liste de string
        /// </summary>
        /// <returns></returns>
        private static IEnumerable<string> GetAllCaractere()
        {
            return _allChars.Select(monChar => monChar.ToString());
        }
    }

Cela est fonctionnel :ccool: ! Et vous n'aurez pas de problème de OutOfMemoryException car vous obtenez avec Linq un IEnumerable

Peut-être que ce code peut être encore simplifié...

18/04/2013, 13h49
k4st0r42

D'après ce que tu as fais Etanne, je crois que je n'ai pas compris le problème pareil.

Il me semble qu'il veut un produit cartésien à n dimensions de sa liste.

EDIT : Ou pas... (Je sais, je me contredis)
18/04/2013, 13h59
Ticoche

Citation:

Envoyé par Bluedeep

Bonjour

Peux tu préciser l'usage de ton aNombreCaractere ? c'est le niveau de multiplication par lui même de ton tableau de caractère ?

Oui, aNombreCaractere est le nombre de fois où la liste doit être multiplier.

Si ma liste est : A, B
et que aNombreCaractere = 1 le résultat attendu sera : A, B
et que aNombreCaractere = 2 le résultat attendu sera : AA, AB, BA, BB
et que aNombreCaractere = 3 le résultat attendu sera : AAA, AAB, ect...
chaque résultat aura un nombre de caractères égale à aNombreCaractere

Je vais étudier la solution de Etanne, merci.

édit: la solution de Etanne correspond bien à mes attentes. Je vais l'adapter à mon cas et tester si je n'ai pas l'exception. En tout cas ton code fonctionne bien. avec 10, c'est atrocement long (plus que ce que j'aurai cru) mais c'est bien le résultat que j'attend. Ce soir je marque [Résolu] si mes tests sont concluant.
Merci beaucoup :)
18/04/2013, 14h50
Ticoche

La solution de Etanne fonctionne très bien, c'est exactement ce que j'attendais.
Maintenant je vais jouer un peu avec les thread pour optimiser le temps de la boucle.

Merci encore

édit: bien que cela fonctionne, je ne comprend pas où est la récursivité ??? Peux-tu détailler les 2 méthodes que tu as écrite afin que je comprenne mieux le mécanisme ?
18/04/2013, 19h51
Etanne
Je vais essayer de bien expliquer :D

Pour cette requête Linq :

Code:

return _allChars.Select(monChar => monChar.ToString());

Ceci est comparable à :
Code:

1 2 3 4 5 6 7 8 9 List<string> listDeChars = new List<string>(); foreach (char monChar in _allChars) { listDeChars.Add(monChar.ToString()); } return listDeChars;
A quelques différence près, c'est que le ma requête Linq ne va pas faire une itération tout de suite, mais uniquement lorsque on en aura besoin.

La MSDN dit :

Citation:

La variable de portée est similaire à la variable d'itération dans une boucle foreach, à la différence qu'aucune itération réelle ne se produit dans une expression de requête. Lorsque la requête est exécutée, la variable de portée servira de référence à chaque élément consécutif

Dans la méthode "MultiplyCaractere" :

Code:

list = from l in list from n in GetAllCaractere() select l + n;

Pour bien comprendre, il faut imaginer que je fasse une jointure SQL de cette forme ci :

Code:

SELECT t1.caractere + t2.caractere FROM AllChars t1, AllChars t2

Et cette jointure est réenregistré dans la variable "list".

Donc je boucle pour autant de caractères dans ma chaîne que je souhaite.

Mon "return list;" ne retournera pas le résultat directement, mais une requête avec n jointure où n représente le nombre de caractères.

Et quand vous appelez :
Code:

1 2 3 4 foreach (var val in list) { Console.WriteLine(val); }
Vous ne faites qu’exécuter la requête construite dans MultiplyCaractere et GetAllCaractere.

J'avoue avoir un peu de mal à bien expliquer par écrit, donc si quelqu'un souhaite me reprendre, je l'encourage (surtout si j'ai écrit n'importe quoi).

Pour bien comprendre mes requêtes Linq, j'imagine toujours travailler avec des requêtes SQL ! Le principe est le même.

Quelques liens dvp :
- http://morpheus.developpez.com/linq/
- http://webman.developpez.com/article...linqtoobjects/
19/04/2013, 09h46
Ticoche

:ccool:
Merci beaucoup Etanne, vraiment parfaite ton explication.
19/04/2013, 11h09
Etanne

De rien !

Petite question, que retourne exactement chez vous GetAllCaractere() ?

Voilà une solution qui utilise la méthode CartesianProduct présentée dans cet article :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var result = Enumerable.Repeat(GetAllCaractere(), nombreCaracteres)
                      .CartesianProduct()
                      .Select(chars => new string(chars.ToArray()));
 
 
...
 
static class Extensions
{
	public 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}));
	}
}

19/04/2013, 15h14
Ticoche

Mon GetAllCaractere() retourne tous les caractères de _allChars, soit :
_allChars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~";

l'avantage, c'est que si j'ai besoin d'ajouter un caractère dans la chaîne, c'est très simple.

Je regarderai également la solution proposé par tomlev, car je dois quand même retoucher l’algorithme pour optimiser les perfs, donc regarder quelle solution est plus souple, je ne vais pas me plaindre d'avoir le choix !!!

Merci
19/04/2013, 17h31
Etanne

La solution de tomlev en utilisant une méthode d'extension et la méthode Linq Aggregate est équivalant sur le résultat et est plus - propre -.

Après question performance je ne saurai dire si c'est équivalant.
19/04/2013, 18h57
tomlev

Citation:

Envoyé par Etanne

Après question performance je ne saurai dire si c'est équivalant.

Il faudrait mesurer, mais je soupçonne que la tienne est un peu plus rapide ; en tous cas elle est plus simple à comprendre ;)

Trouvant le problème intéressant, j'ai réfléchit un petit peu à une solutions (en me disant qu'il faudrait que le code soit facilement parallélisable)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
    class Program
    {
        static void Main(string[] args)
        {
            string test = "abcdefghijklmnopqrstuvwxyz";
            foreach(string item in mult(test.ToCharArray(),3))
                Console.WriteLine(item);
            Console.Read();
        }
 
        public static IEnumerable<string> mult(char[] chars, int nb)
        {
            int nbChar = chars.Length-1;
            int[] cmpts = new int[nb];
            //Initialisation des compteurs
            for (int i = 0; i < nb; i++)
            {
                cmpts[i] = nbChar;
            }
 
            char[] res = new char[nb];
            nb--;
 
            while (cmpts[0] >= 0)
            {
                res[nb] = chars[cmpts[nb]];
                cmpts[nb]--;
                for (int i = nb - 1; i >= 0; i--)
                {
                    res[i] = chars[cmpts[i]];
                    if (cmpts[i+1] < 0)
                    {
                        cmpts[i + 1] = nbChar;
                        cmpts[i]--;
                    }
                }
                yield return new string(res);
            }
        }
    }

en rajoutant des paramètres, on peut facilement diviser le travail sur plage de valeur pour le compteur à l'index 0.

Ma solution est sans récursivité et peut-être pas aussi élégante que les autres solutions proposé mais est peut-être plus facilement parallélisable.

Sinon pour la solutions de Etanne, il peut il y avoir un "petit" gain de perfomances si on évite les concaténations de chaines. (Je dirais
26^9 concaténation dans son exemple)

24/04/2013, 15h00
antoine.debyser

Bonjour,

On m'a un jour posé un problème similaire lors d'un entretiens.
Et la solution proposé (par l'examinateur) était pour moins original, utiliser un tableau d'index.

Les valeurs contenus dans le tableau, indique la position du caractère à utiliser.
Pour la génération, il suffit de faire varier une case de 0 à N (N represantant la taille de l'ensemble de caractère). Une fois N ateint, on repasse la case à 0 et on passe à la case suivante.

J'essaierai de poster une implémentation dans les jours à venir.