Discussion :

[Ticoche]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[k4st0r42]

Ça risque d'être compliqué ce que tu veux faire avec un yield

[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 !

[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 ?

[Etanne]

Bonjour,

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

Voici ma solution avec Linq:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ! 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é...

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

[Ticoche]

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

[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 ?

[Etanne]

Je vais essayer de bien expliquer

Pour cette requête Linq :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Ceci est comparable à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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/

[Ticoche]

Merci beaucoup Etanne, vraiment parfaite ton explication.

[Etanne]

De rien !

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

[tomlev]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

[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.

[tomlev]

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

[g.Arnaud]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[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.