[Algorithme] genre factorielle ?

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonjour,

Je ne sais pas trop comment expliquer mon problème, commençons par le début : J'utilise Visual Studio Express 2008, je crois que la librairie pour utiliser la classe Exponential n'est pas disponible ?!
Bref, je me suis fait la méthode qui à l'air de bien fonctionner
Code:

1 2 3 4 5 6 7 8 9 10 11 private int exponentielle(int nombre) { int locale = 1; while (nombre > 1) { locale *= nombre--; } return locale; }
Bon, mais après, voila mon vrai problème. Je cherche un algorithme me permettant de calculer toute les combinaisons possible pour croisé des lettres, je m'explique :
J'ai toujours 3 séries de lettres, les 3 série comportent toujours le même nombre de lettre (peuvent même être identique et donc y avoir des doublons) et j'aimerai par exemple à partir de :
liste 1 : A B C
liste 2 : D E F
liste 3 : G H I

Obtenir le tableau de résultat suivant :
ABC
ABF
ABI
AEC
AEF
AEI
AHC
AHF
AHI
DBC
[...]
GHC
GHF
GHI

sachant que les lettres A D G seront toujours en position 1
les lettres B E H seront toujours en position 2
et C F I toujours en position 3

Je me suis dit que pour un tel calcul j'aurai besoin de la fonction exponentielle, mais j'arrive pas à obtenir le bon resultat ?!

Si je suis asser clair, est-ce qu'on peut m'aider sur la manière de procéder ?

Merci

04/05/2008, 14h11
harz62

La méthode statique de la classe Math réalise cette fonction: Math.Exp

Visual Studio ne limite pas l'utilisation des classes du framework. Le framework lui est gratuit et donc tu peux même utiliser les classes du framework sans avoir besoin de développer avec Visual Studio.

Visual Studio est seulement l'environnement qui convient le mieux pour développer des applications mais il ne limite en aucun cas l'utilisation des classes du framework. La différence des versions tient aux fonctionnalités qu'il proposent.

Citation:

Envoyé par harz62

La méthode statique de la classe Math réalise cette fonction: Math.Exp

Visual Studio ne limite pas l'utilisation des classes du framework. Le framework lui est gratuit et donc tu peux même utiliser les classes du framework sans avoir besoin de développer avec Visual Studio.

Visual Studio est seulement l'environnement qui convient le mieux pour développer des applications mais il ne limite en aucun cas l'utilisation des classes du framework. La différence des versions tient aux fonctionnalités qu'il proposent.

En fait Math.exp n'est pas la fonction exponentielle ?!
par exemple :
3! = 6
4! = 24
5! = 120
etc...
Mais ce n'est pas du tout mon problème, j'ai fait la fonction exponentielle qui fonctionne très bien.

Maintenant je ne sais même pas si je pars dans le bon sens, ce que j'ai c'est des lettres (dans des listes) et j'aimerai obtenir toute les combinaisons possible, voici un bout de mon code :
Code:

1 2 3 4 5 6 List<string> lstSyllabes1 = new List<string>(); List<string> lstSyllabes2 = new List<string>(); List<string> lstSyllabes3 = new List<string>(); [...] combinaisons = getCombinaisons(lstSyllabes1, lstSyllabes2, lstSyllabes3);
Ma fonction accepte 3 arguments qui sont des List<string>.
typiquement, une List<string> peut resembler à ça :
L
ou
L + R
ou
M + R + T
ou
CH + J + P + V
ou
etc...

et j'aimerai qu'elle retourne une List<List<string>> où chaque List<string> serait une combinaison des 3 arguments (voir exemple précédant)

Mon problème ce situe au niveau de l'algorithme permettant justement de trouver toutes ces combinaisons (le nombre de string dans la liste peut varié, mais les 3 listes en comporte le même nombre)

Merci

04/05/2008, 16h28
tomlev

C'est pas ça la fonction Exponentielle... ce dont tu parles ça s'appelle "factorielle", c'est le produit de tous les entiers de 1 à N. Je ne crois pas que la fonction existe nativement, mais le code que tu mets dans ton premier post me semble correct (à part le nom de la fonction...)
04/05/2008, 16h54
Ticoche
Citation:

Envoyé par tomlev

C'est pas ça la fonction Exponentielle... ce dont tu parles ça s'appelle "factorielle", c'est le produit de tous les entiers de 1 à N. Je ne crois pas que la fonction existe nativement, mais le code que tu mets dans ton premier post me semble correct (à part le nom de la fonction...)

Heu... oui, c'est factorielle... un gros lapsus !!! :oops:

Je penses que j'aurai autant de résultat que x! où x est le nombre de string. Mais j'arrive toujours pas à créer correctement l'algo me permettant de mettre la main sur tous ces résulats.

Pour rendre le code plus souple, j'ai changé la signature de ma methode :
Code:

1 2 private List<List<string>> getCombinaisons(List<List<string>> lstSyllabes)

Bonjour,
si j'ai bien compris, tu cherches l'algorithme permettant de construire toute les combinaisons possibles de tes 3 listes. Tu peux y parvenir simplement en faisant des boucles imbriquées :

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
 
 
            int i, j, k, n, nbelem;
            List<string> liste1 = new List<string>();
            List<string> liste2 = new List<string>();
            List<string> liste3 = new List<string>();
            List<List<string>> res = new List<List<string>>();
 
            liste1.Add("A"); liste1.Add("B"); liste1.Add("C");
            liste2.Add("A"); liste2.Add("B"); liste2.Add("C");
            liste3.Add("A"); liste3.Add("B"); liste3.Add("C");
 
            nbelem = liste1.Count;
            n = 0;
 
            for (i = 0; i < nbelem; i++)
                for (j = 0; j < nbelem; j++)
                    for (k = 0; k < nbelem; k++)
                    {
                        res.Add(new List<string>());
                        res[n].Add(liste1[i]);
                        res[n].Add(liste2[j]);
                        res[n].Add(liste3[k]);
                        n++;
                    }
 
            string s="";
            for (i = 0; i < res.Count; i++)
                s += res[i][0] + res[i][1] + res[i][2] + "\n";

La liste résultat est res, affichée dans la chaine s pour l'exemple.

Citation:
Envoyé par clochettes
Bonjour,
si j'ai bien compris, tu cherches l'algorithme permettant de construire toute les combinaisons possibles de tes 3 listes. Tu peux y parvenir simplement en faisant des boucles imbriquées :
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 int i, j, k, n, nbelem; List<string> liste1 = new List<string>(); List<string> liste2 = new List<string>(); List<string> liste3 = new List<string>(); List<List<string>> res = new List<List<string>>(); liste1.Add("A"); liste1.Add("B"); liste1.Add("C"); liste2.Add("A"); liste2.Add("B"); liste2.Add("C"); liste3.Add("A"); liste3.Add("B"); liste3.Add("C"); nbelem = liste1.Count; n = 0; for (i = 0; i < nbelem; i++) for (j = 0; j < nbelem; j++) for (k = 0; k < nbelem; k++) { res.Add(new List<string>()); res[n].Add(liste1[i]); res[n].Add(liste2[j]); res[n].Add(liste3[k]); n++; } string s=""; for (i = 0; i < res.Count; i++) s += res[i][0] + res[i][1] + res[i][2] + "\n";
La liste résultat est res, affichée dans la chaine s pour l'exemple.
Merci, je vais tester ça !

En fait, l'algo est le même que mon 1er test, j'avais fait pareil sauf que je ne veut pas boucler de cette manière, je m'explique...
Comme il y a 3 listes et chacune comprend 3 elements ça porte à confusion, mettons 4 elements dans chaque liste (je rappelle que le nombre d'élement est variable, mais identique pour chaque liste)
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 int i, j, k, n, nbelem; List<string> liste1 = new List<string>(); List<string> liste2 = new List<string>(); List<string> liste3 = new List<string>(); List<List<string>> res = new List<List<string>>(); liste1.Add("A"); liste1.Add("B"); liste1.Add("C"); liste1.Add("D"); liste2.Add("E"); liste2.Add("F"); liste2.Add("G"); liste2.Add("H"); liste3.Add("I"); liste3.Add("J"); liste3.Add("K"); liste3.Add("L"); nbelem = liste1.Count; n = 0; for (i = 0; i < nbelem; i++) for (j = 0; j < nbelem; j++) for (k = 0; k < nbelem; k++) { res.Add(new List<string>()); res[n].Add(liste1[i]); res[n].Add(liste2[j]); res[n].Add(liste3[k]); n++; } string s = ""; for (i = 0; i < res.Count; i++) { s += res[i][0] + res[i][1] + res[i][2] + " - "; }
Le jeu de résultat obtenu est :

Citation:

AEI - AEJ - AEK - AEL - AFI - AFJ - AFK - AFL - AGI - AGJ - AGK - AGL - AHI - AHJ - AHK - AHL - BEI - BEJ - BEK - BEL - BFI - BFJ - BFK - BFL - BGI - BGJ - BGK - BGL - BHI - BHJ - BHK - BHL - CEI - CEJ - CEK - CEL - CFI - CFJ - CFK - CFL - CGI - CGJ - CGK - CGL - CHI - CHJ - CHK - CHL - DEI - DEJ - DEK - DEL - DFI - DFJ - DFK - DFL - DGI - DGJ - DGK - DGL - DHI - DHJ - DHK - DHL -

Alors que ce que je souhaite doit ressembler à :

Citation:

ABCD - ABCH - ABCL - ABGD - ABGH - ABGL - ABKD... Etc

d'où la difficulté, car avec 3 éléments on boucle 3 fois, avec 4 ou 5 ou plus on doit boucler d'autant plus pour avoir un résultat du genre :
ABCDE - ABCDJ - ABCDO - etc...

soit, un nombre de boucle variable !
c'est toujours possible, maintenant que je me suis mieux expliqué ?

Merci ;)

édit:
Je vais modifier le remplissage des listes, pour que l'algo proposé par clochettes fonctionne, je devrais donc avoir n listes de 4 elements.
Je me demande si une fonction récurssive ne pourrait pas réussir à régler le problème du nombre de boucles variables ?

06/05/2008, 10h51
Ticoche

forcément, je dois m'y prendre mal j'ai l'exception StackOverFlow.

Comment on peut faire pour que les 3 boucles puissent être modulable en n boucles ?
Je penses toujours qu'avec une methode récurssive on peut y arriver, mais voilà, seulement comment faire ?

Merci
06/05/2008, 10h53
Guulh

Citation:

Envoyé par Ticoche

forcément, je dois m'y prendre mal j'ai l'exception StackOverFlow.

Comment on peut faire pour que les 3 boucles puissent être modulable en n boucles ?
Je penses toujours qu'avec une methode récurssive on peut y arriver, mais voilà, seulement comment faire ?

Merci

Tu passes en paramètres de ta fonction récursive en entier n qui indique le nombre restant de valeurs à mettre dans ton chaîne : f(..., 4) appelle f(..., 3), qui appelle f(..., 2), ...
Et f(..., 0) est la fin de l'appel récursif.
'fin la base de la récursivité quoi :)

ça à l'air simple... mais j'arrive pas à obtenir l'effet souhaité.
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 int tour = 0; private List<List<string>> getCombinaisons(List<List<string>> lstSyllabes) { List<List<string>> locale = new List<List<string>>(); List<string> tampon = new List<string>(); creationRecursive(ref tampon, lstSyllabes, lstSyllabes.Count); locale.Add(tampon); return locale; } private void creationRecursive(ref List<string> resultat, List<List<string>> desordre, int boucle) { if (tour < boucle) { resultat.Add(desordre[tour][0]); tour++; creationRecursive(ref resultat, desordre, desordre.Count); } if (tour == boucle) tour = 0; }
J'ai réussis à obtenir ainsi la 1ère combinaison, mais je n'arrive pas à "brasser" toute les combinaisons, je ne voit pas où placer l'algorithme ?!

l'argument lstSyllabes est composé de n listes correctement rempli où chaque liste est une list<string>
J'ai choisi (finalement) de placer les éléments ainsi
liste1: A+B+C+D (exclusivement 4 string)
liste2: E+F+G+H (exclusivement 4 string)
listeN: ... (exclusivement 4 string)
listeN+1: W+X+Y+Z (exclusivement 4 string)
(minimum 1 liste, pas de limite maximum)

Pour le moment j'arrive à obtenir la combinaison : A+E+...+W, il me manque "juste" les autres !!!
Je crois bien que si je laisse desordre[tour][0] je n'arriverai jamais à obtenir toutes les combinaisons, mais je ne vois pas non plus comment arranger ça ?

Si vous avez une solution, même completement différente, je tourne en rond !

Merci

Un truc genre ça ?

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
 
public string[] combinaisons(string initial, string[] keys)
        {
            if (keys.Length < 1)
                return new string[] { initial };
 
            List<string> result = new List<string>();
 
            List<string> sub_keys = new List<string>();
            foreach (string key in keys)
            {
                sub_keys.Clear();
                sub_keys.AddRange(keys);
                sub_keys.Remove(key);
 
                result.AddRange(combinaisons(initial + key, sub_keys.ToArray()));
            }
 
            return result.ToArray();
        }
 
        private void button1_Click(object sender, EventArgs e)
        {
            string[] comb = combinaisons("", new string[] { "A", "B", "C", "D", "E" });
        }

07/05/2008, 07h25
Ticoche

Ton algorithme donne bien toutes les combinaisons possibles pour une liste (d'ailleur le nombre de résultat est bien factorielle au nombre d'elements dans cette liste), il me reste plus qu'à l'adapter pour donner les combinaisons sur plusieurs listes au lieu d'une seule.

Merci beaucoup, ça donne bon espoir :D

J'ai presque ma solution
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 private List<string> getCombinaisons(List<List<string>> lstSyllabes) { List<string> locale = new List<string>(); locale = combinaisons("", lstSyllabes); return locale; } public List<string> combinaisons(string initial, List<List<string>> keys) { if (keys.Count < 1) { List<string> locale = new List<string>(); locale.Add(initial); return locale; } List<string> result = new List<string>(); List<List<string>> sub_keys = new List<List<string>>(); foreach (List<string> lstKey in keys) { foreach (string key in lstKey) { sub_keys.Clear(); sub_keys.AddRange(keys); sub_keys.Remove(lstKey); result.AddRange(combinaisons(initial + key, sub_keys)); } } return result; }
Du coup, maintenant j'ai "trop" de combinaisons ! Par exemple, quand je passe 2 listes qui ressembles à :
liste1 : T+D
liste2: N
(oui, il peut y avoir n listes de x chaines maintenant, puisque c'est possible)

J'obtiens les résultats suivant :
T+N
D+N
N+T
N+D
alors que les résultats en rouge ne m'interresse pas (NT et ND) !
Certes, pour le moment je pourrai repasser une autre fois sur les résultats et supprimer ceux qui m'interresse pas, mais ça serait plus simple de ne pas les ajouter, non ? Comme j'ai vraiment beaucoup de mal avec la récursivité, j'aimerai savoir où je dois faire une modification ?

Je penses que ça se passe ici :
Code:

1 2 3 4 5 6 7 8 9 10 11 foreach (List<string> lstKey in keys) { foreach (string key in lstKey) { sub_keys.Clear(); sub_keys.AddRange(keys); sub_keys.Remove(lstKey); result.AddRange(combinaisons(initial + key, sub_keys)); } }
En fait il ne faut pas faire "glisser" les lettres d'une liste vers la gauche.
Si j'ai un élément dans la liste1 (indice 0) il sera forcément en position [0] dans le résultat, il ne doit pas changer de place, ceux de la liste 2 (indice 1) seront toujours en position [1] dans le résultat, etc... (également valable pour les autres positions)

voila, j'avance bien, merci smyley

Et si au lieu de faire :

Code:

1
2
3
4
5
6
7
8
9
10
foreach (List<string> lstKey in keys)
            {
                foreach (string key in lstKey)
                {
                    sub_keys.Clear();
                    sub_keys.AddRange(keys);
                    sub_keys.Remove(lstKey);
                    result.AddRange(combinaisons(initial + key, sub_keys));
                }
            }

tu fais :

Code:

1
2
3
4
5
6
7
8
9
10
foreach (List<string> lstKey in keys)
            {
                foreach (string key in lstKey)
                {
                    sub_keys.Clear();
                    sub_keys.AddRange(keys);
                    sub_keys.Remove(key);
                    result.AddRange(combinaisons(initial + key, sub_keys));
                }
            }

? (subtile différence entre lstKey et key :aie:)

09/05/2008, 22h53
Ticoche
Oula, j'ai fais tellement de modif dans la méthode, si je touche le moindre petit truc ça créé des interferences monstrueuses, et avec la récursivité ça n'arrange rien
Code:

1 2 List<List<string>> sub_keys = new List<List<string>>();
en gros, ce qui me dérange le plus c'est le type de retour, et je me prends la tête #$<~&! pour avoir une List<List<string>> en retour !

Car je dois encore manipuler chaque résultat, et je me retrouve avec :
résultat: chnj
alors que j'attends :
résultat: ch+n+j (par exemple)

Comme j'ai vraiment du mal avec la récursivité, pour le moment je garde List<string> en retour et j'essaie de repasser dessus pour re-séparer les syllabes, mais c'est quasi-impossible en fait :bug:

Si je pouvais arriver à un résultat comme ça :
Code:

1 2 3 4 public List<List<string>> combinaisons(unType unTrucOuRien, List<List<string>> keys) { }
je crois que dans la méthode de base il faudrait remplacer "string initiale" par "List<string> initiale" avec toutes les conséquences que ça implique :aie:

édit: et j'avoue que je me prends pas mal la tête avec ce problème en ce moment.
09/05/2008, 22h57
smyley

Bon, par étape.
Déjà tu veux vraiment qu'il y ai un "+" entre chaque élément ?
dans ce cas c'est juste remplacer

Code:

initial + key

par

Code:

initial + "+" + key

non ?
09/05/2008, 23h57
Ticoche

Citation:

Envoyé par smyley

Bon, par étape.
Déjà tu veux vraiment qu'il y ai un "+" entre chaque élément ?
dans ce cas c'est juste remplacer

Code:

initial + key

par

Code:

initial + "+" + key

non ?

Non non, le "+" c'est pour symboliser chaque élément dans la liste.

Quand je met :
J+N
il faut comprendre, une List<string> qui comprend 2 éléments "J", et "N"

après :
CH+QU+M (3 strings CH et QU et M)

et donc, le résultat doit être une liste de tout ça :
List<List<string>>
qui comprend (dans mon exemple) J+N et CH+QU+M

En fait j'ai remarqué que depuis le début je donne des exemples avec une seule lettre, mais finalement un résultat est formé de plusieurs syllabes, donc plusieurs lettres "collés" qui doivent le rester (sinon j'aurai choisi un char)

J'en rêve la nuit, ça me hante, il faut bien que j'arrive à trouver la solution un jour ou l'autre !

En tout cas merci pour ton aide :D

Dans ce cas essaye ça (j'aurai bien aimé que ça marche, j'ai du réfléchir :aie:)

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
42
43
44
45
46
47
48
49
50
51
52
 
public int[][] i_combinaisons(int nb_a_prendre, int start, int max)
        {
            if (nb_a_prendre == 1)
            {
                List<int[]> result = new List<int[]>();
                for (int i = start; i <= max; i++)
                {
                    result.Add(new int[] { i });
                }
                return result.ToArray();
            }
            else
            {
                List<int[]> result = new List<int[]>();
 
                int[][] this_level = i_combinaisons(nb_a_prendre - 1, start + 1, max);
                foreach (int[] item in this_level)
                {
                    int[] val = new int[item.Length + 1];
                    val[0] = start;
                    for (int i = 0; i < item.Length; i++)
                    {
                        val[i + 1] = item[i];
                    }
                    result.Add(val);
                }
 
                if (start + 1 <= max - nb_a_prendre)
                {
                    result.AddRange(i_combinaisons(nb_a_prendre, start + 1, max));
                }
 
                return result.ToArray();
            }
        }
 
        public string[][] combinaisons(string[] keys, int keys_per_item)
        {
            int[][] indexes = i_combinaisons(keys_per_item, 0, keys.Length-1);
            string[][] result = new string[indexes.Length][];
            for (int i = 0; i < indexes.Length; i++)
            {
                result[i] = new string[keys_per_item];
                for (int j = 0; j < keys_per_item; j++)
                {
                    result[i][j] = keys[indexes[i][j]];
                }
            }
 
            return result;
        }

Utilisation :
string[][] comb = combinaisons(new string[] { "A", "B", "C", "D", "E"}, 3);

Renvoi tous les combinaisons de 3-couples de l'ensemble A,B,C,D,E sans ordre, enfin, en théorie.

10/05/2008, 08h03
Ticoche

Je vais essayé ça... mais j'ai un doute sur le paramètre d'entrée "string[] keys", pour moi en entrée il faut obligatoirement un tableau à 2 dimentions ou (ce que je préfère) une List<List<string>>.

Prenons un exemple concré :

En amont j'obtiens cette liste :
List<List<string>> lstSyllabes qui contient 3 listes (pour l'exemple):
c+k+q+g (liste de 4 éléments)
f+v (liste de 2 éléments)
j+ch (liste de 2 éléments)
Je peux obtenir de 1 liste à N listes.

Quels résultats ai-je envi d'obtenir ?
1er cas : disons qu'il n'y a que la 1ère liste
résultat: c
résultat: k
résultat: q
résultat: g
c'est tout ! (1 liste <=> 1 syllabe)

2ème cas : disons qu'il y a 2 listes
résultat: c+f
résultat: c+v
résultat: k+f
résultat: k+v
résultat: q+f
résultat: q+v
résultat: g+f
résultat: g+v
c'est tout ! (2 listes <=> 2 syllabes)

3ème cas : Il y a 3 listes, comme dans l'exemple
résultat: c+f+j
résultat: c+f+ch
résultat: c+v+j
résultat: c+v+ch
résultat: k+f+j
résultat: k+f+ch
résultat: k+v+j
résultat: k+v+ch
résultat: q+f+j
résultat: q+f+ch
résultat: q+v+j
résultat: q+v+ch
résultat: g+f+j
résultat: g+f+ch
résultat: g+v+j
résultat: g+v+ch
c'est tout ! (3 listes <=> 3 syllabes)

On remarque que la liste1 est toujours en position[0] dans chaque résultat, que la liste2 est toujours en position[1], et la liste3 en position[2], cela signifie que la liste1 contient la 1ère syllabe, la liste2 la syllabe suivante et la liste3 la dernière syllabe, voila pourquoi il ne faut pas les mélangés plus que ça.
Par la suite, je dois encore faire un algorithme me permettant d'ajouter ou pas des voyelles entre chaque syllabe (mais ça ne devrait pas me poser problème cette partie)

merci, je vais regarder de près ton algo maintenant

édit: Je suis en train de me rendre compte, qu'avec des tableaux à 2 dimensions, par définition il faut définir length et la capacité de chaque élément, or mes listes ne sont pas homogène et comporte des fois 2, 3 ou 4 element, ce qui retourne des valeurs null dans le tableau.
J'ai converti ma List<List<string>> en string[,] et je vais la passer dans la methode pour voir...

édit: Bon en fait j'ai l'impression d'être bloqué. Comme je le pensais, l'argument d'entré ne correspond pas au bon format, il lui manque une dimension, sinon je suis obligé de refaire un découpage impossible ! :cry:
je continu à chercher...
10/05/2008, 17h13
smyley

mais tu ne peut pas simplement fusionner toutes les listes en une seule ?!

Voir 40 message(s) de cette discussion en une page