Calcul combinaison avec exception/alias — Les-mathematiques.net The most powerful custom community solution in the world

Calcul combinaison avec exception/alias

Bonjour.
Je me permets de venir poster sur ce forum pour vous soumettre un problème mathématique que je ne parviens pas à solutionner.

Je vous soumets le contexte.
Je suis actuellement en train de développer un programme qui génère un dictionnaire de mot de passe à partir d'une liste de mots donnée. Le but étant de générer toutes les permutations possibles (permutation compris), selon un intervalle (la taille de la concaténation) et sans qu'il n'y air de doublon dans la génération.

Par exemple la liste suivante.
alice
bob
carole
dave

Le résultat après génération sur un intervalle 2 3 (2=concaténation minimum, 3=concaténation maximum).
alicebob
bobalice
alicecarole
carolealice
alicedave
davealice
bobcarole
carolebob
bobdave
davebob
caroledave
davecarole
alicebobcarole
alicecarolebob
bobalicecarole
bobcarolealice
carolebobalice
carolealicebob
alicebobdave
alicedavebob
bobalicedave
bobdavealice
davebobalice
davealicebob
alicecaroledave
alicedavecarole
carolealicedave
caroledavealice
davecarolealice
davealicecarole
bobcaroledave
bobdavecarole
carolebobdave
caroledavebob
davecarolebob
davebobcarole

Nombre de lignes = 36

Mon but est de prédire le nombre de lignes par le calcul et ici c'est simple.
total = (total_ligne * total_ligne-1) + (total_ligne * total_ligne-1 * total_ligne-2)
total = (4 * 3) + (4 * 3 * 2)
total = 36
La première parenthèse calcule l'intervalle 2 et la seconde intervalle 3.

Bien, mais à l'heure actuelle, j'ai ajouté une nouvelle fonctionnalité à mon programme: les alias.

Les alias sont des synonymes aux mots. De ce fait, lors de la génération nous ne pouvons pas retrouver deux synonymes (alias) ensemble.

Voici l'exemple de la liste avec les alias:
alice|lili|lily
bob
carole|caro
dave

Prenons toujours un intervalle 2 3:
alicebob
bobalice
alicecarole
carolealice
alicecaro
caroalice
alicedave
davealice
lilibob
boblili
lilicarole
carolelili
lilicaro
carolili
lilidave
davelili
lilybob
boblily
lilycarole
carolelily
lilycaro
carolily
lilydave
davelily
bobcarole
carolebob
bobcaro
carobob
bobdave
davebob
caroledave
davecarole
carodave
davecaro
alicebobcarole
alicecarolebob
bobalicecarole
bobcarolealice
carolebobalice
carolealicebob
alicebobcaro
alicecarobob
bobalicecaro
bobcaroalice
carobobalice
caroalicebob
alicebobdave
alicedavebob
bobalicedave
bobdavealice
davebobalice
davealicebob
alicecaroledave
alicedavecarole
carolealicedave
caroledavealice
davecarolealice
davealicecarole
alicecarodave
alicedavecaro
caroalicedave
carodavealice
davecaroalice
davealicecaro
lilibobcarole
lilicarolebob
boblilicarole
bobcarolelili
caroleboblili
carolelilibob
lilibobcaro
lilicarobob
boblilicaro
bobcarolili
caroboblili
carolilibob
lilibobdave
lilidavebob
boblilidave
bobdavelili
daveboblili
davelilibob
lilicaroledave
lilidavecarole
carolelilidave
caroledavelili
davecarolelili
davelilicarole
lilicarodave
lilidavecaro
carolilidave
carodavelili
davecarolili
davelilicaro
lilybobcarole
lilycarolebob
boblilycarole
bobcarolelily
caroleboblily
carolelilybob
lilybobcaro
lilycarobob
boblilycaro
bobcarolily
caroboblily
carolilybob
lilybobdave
lilydavebob
boblilydave
bobdavelily
daveboblily
davelilybob
lilycaroledave
lilydavecarole
carolelilydave
caroledavelily
davecarolelily
davelilycarole
lilycarodave
lilydavecaro
carolilydave
carodavelily
davecarolily
davelilycaro
bobcaroledave
bobdavecarole
carolebobdave
caroledavebob
davecarolebob
davebobcarole
bobcarodave
bobdavecaro
carobobdave
carodavebob
davecarobob
davebobcaro

Total: 136 lignes.

Mon problème est le suivant. Je n'arrive plus à prédire par le calcul le nombre de mots finaux avec la nouvelle façon de générer mes mots...
Quelqu'un a-t-il une solution ou une piste pour ce problème ?
Merci d'avance.
Cordialement,
Tatam.

Réponses

  • Bonsoir,
    On se donne donc $n$ personnes numérotées de $1$ à $n$ et on note $x_i$ le nombre de noms que possède la personne numérotée $i$. $(1\leq i \leq n,\:\: x_i\geq1)$.
    On définit les entiers $a_0,a_1,\dots a_n$ comme les coefficients du polynôme $P(X) = \displaystyle{\prod_{i=1}^{n}(X+x_i) = \sum _{k=0}^{n} a_k X^{n-k}}$.
    Dans ton dernier exemple: $x_1 =3;\: x_2= 1;\:x_3=2;\:x_4 =1 $ et donc $ a_0 =1 ; \:a_1 = 7;\: a_2 =17 ; \:a_3 =17;\:a_4 =6$.
    (car $ (X+3)(X+1)(X+2)(X+1)= X^4 +7X^3+17X^2+17X+6$.)
    Le nombre $N_p$ de mots de passe qu' il est possible d'obtenir lorsque on impose à ceux-ci de contenir exactement $p$ noms est: $\boxed { N_p = p!\: a_p}$ .
    Ainsi, si le nombre de noms figurant dans un mot de passe est compris entre $p$ et $q$, alors le nombre de mots de passe est: $N=\displaystyle{\sum_{k=p}^q N_k}$.
    (Dans ton exemple: $N = N_2 + N_3 = 2!\:a_2 + 3!\:a_3= (1\times2\times17) +(1\times2\times3\times17) =136$.)

    Amicalement,
  • Bonjour LOU16.

    Un grand merci pour cette réponse détaillée.

    N'étant pas très doué pour les formules mathématiques, je ne comprend pas comment tu calcul les coefficients du polynôme (notée a): P(X)

    Pourrais-tu détailler ce calcul pour le néophyte que je suis ?

    Merci d'avance,
    Tatam.
  • Re,

    J' applique les propriétés de "distributivité" et d' "associativité" dans le "développement" du produit $(X+3) (X+1) (X+2)(X+1)$ que je vais détailler ci-dessous, en m'efforçant de ne pas être trop nébuleux.
    $P(X)= (X+x_1)(X+x_2)(X+x_3)(X+x_4)\:\:\:\:\:\:$ (c'est la définition de $P(X)$.)
    $P(X) =(X+3)(X+1)(X+2)(X+1) = \left[(X+3)(X+1)\right]\left[(X+2)(X+1)\right]= (X^2 +X+3X+3)(X^2+X+2X+2)$
    $P(X) = (X^2+4X+3)(X^2+3X+2)$
    $P(X)= X^4+3X^3+2X^2+4X^3+12X^2+8X+3X^2+9X+6$
    $P(X) = X^4 + (3+4)X^3 +(2+12+3)X^2 + (8+9)X+6 $
    $P(X)= X^4+7X^3 +17X^2+17 X+6.$
    Ainsi $a_0=1 $ (coefficient de $X^4$), $a_1 = 7$ (coefficient de $X^3$), $a_2 =17$, $a_3=17$ et $a_4=6$ .
    Amicalement,
  • Re bonjour LOU16 et encore merci pour ton temps.
    Je comprends maintenant le calcul de P(X).
    J'ai cependant une question qui va sûrement te sembler bête.

    Comme dit dans mon premier poste, je compte utiliser ces calculs dans un langage informatique (en C), or il est assez difficile de traduire des inconnues (ici X) en programmation. Ma question est la suivante: les inconnues ne peuvent-elle pas être évitées ?

    Par ailleurs, dans ton exemple, tu calcules l’ensemble des coefficients à savoir X4+7X3+17X2+17X+6. X4 pour le premier intervalle, 7X3 pour le second etc.
    N'est-il pas possible de calculer seulement pour les intervalles voulu ? Je pause cette question car il n'est pas impossible que j'ai plus de 100 mots dans l'utilisation finale de mon programme.

    Merci d'avance,
    Tatam.
  • Re
    Afin que je puisse te donner des explications susceptibles d' être comprises pour un éventuel algorithme calculant les nombres $a_1,a_2, ...a_n$,, il serait bon que je sache en quelle classe tu es.
    D' autre part, tu dois d'ores et déjà te concentrer davantage sur le vocabulaire que j' utilise:
    $\boxed{a_k \text{ est le coefficient de }X^{n-k}\text{ dans le développement de } P(X) =(X+x_1)(X+x_2)\dots(X+x_n).}$
    Ainsi, lorsque $P(X) = (X+3)(X+1)(X+2)(X+1) = X^4 +7X^3+ 17X^2+17X+6$, on est dans une situation où:
    $n=4$ donc $a_1$ est le coefficient de $X^{4-1}=X^3$ , c'est à dire :$a_1$ est le nombre par lequel est multiplié $X^3$ .Ainsi:$\:\:\underline{a_1 =7}$ (et non $a_1=7X^3)$
    $a_2$ est le coefficient de $X^{4-2}=X^2$, donc $a_2 = 17\:\:\:$ etc...

    Amicalement
  • Re

    Et bien je ne suis en aucune classe, je suis un informaticien qui code le week-end une appli pour le plaisir. Mais j'imagine que tu veux sans doute connaître mon niveau en mathématique. Il n'est pas très élevé pour être honnête, je dirais niveau lycée.
    Après je suis capable de comprendre, mais il me manque beaucoup de bases...

    Pour le vocabulaire, désolé, je vais faire en sorte de faire plus d’effort.

    Tatam.
  • Re

    Je peux donc t'indiquer un algorithme qui prend en entrée les entiers $x_1,x_2,...x_n$ , les bornes $p$ et $q$ de l'intervalle de concaténation ($1\leq p\leq q\leq n$) et produit en sortie le nombre $N$ de "codes" possibles.Le voici:
    $\bullet$ Entrer les entiers $x_1,x_2... x_n$ $p,q$.
    $\bullet$ Donner à $a_0$ la valeur $1$ et à $a_1,a_2 ... a_n$ la valeur $0$.
    $\bullet$ Donner à $N$ la valeur $0$.
    $\bullet$ $\left[ \begin{array}{l} \text{Pour i allant de 1 à n}\\ \left[\begin {array}{l} \text{Pour k allant de 0 à i-1}\\ a_{i-k}\:
    \text{prend la valeur} \:a_{i-k }+(x_i\times a_{i-k-1})\\ \text{Fin du Pour}\\ \end{array}\right. \\ \text {Fin du Pour}\\ \end{array} \right.$

    $\bullet \left[\begin{array}{l} \text {Pour i allant de p à q}\\ N\: \text{ prend la valeur} \:N+( i! \times a_i) \\\text{Fin du Pour}\\ \end{array}\right.$
    $\bullet\:\text{Afficher }N$

    Amicalement
  • Re.

    Génial ! J'ai fait un POC de mon côté et le code est fonctionnel.

    Je pense cependant qu'il y a une légère coquille dans ton algo:
    ai-k prend la valeur ai-k + (xi x ai-k-1)

    En effet, lorsque le symbole est +, il n'y à que des multiplications par 0 du fait que l'indice de a est toujours > à 1.

    Dans tous les cas, un grand merci pour ton aide et ta patience.

    Tatam.
  • Re,

    Merci pour le signalement de cette erreur que je corrige. Je croyais pourtant avoir été bien concentré au moment de recopier le code de l' algorithme que j'avais testé et qui fonctionnait correctement.

    Amicalement,
  • Re.

    Je viens d'implémenter l'algo dans mon programme en C et après pas mal d'essai je viens de remarquer un petit problème.

    Lorsqu'il n'y a qu'un seul alias sur une longue suite de mots, le résultat est erroné.

    Par exemple pour un intervalle 2 3 avec les mots suivants:
    alice
    bob
    carole
    dave
    eddy
    fany|fafa
    gael

    Ici, le calcul prédit 54 mots, or 354 mots sont générés (pas de doublon j'ai vérifie).

    Par ailleurs, j'ai remarqué en faisait plusieurs test qu'il manquait toujours un multiple de 10. (Toujours lorsque les alias sont nettement inférieur aux nombres de noms).

    J'ai un problème similaire lorsque j'ai 0 alias, mais la, c'est de ma faute, je ne l'avais pas spécifié au départ qu'il pouvais ne pas y avoir d'alias.

    As-tu une idée pour ce problème ? Algo ? Implémentation ?

    Merci d'avance,
    Tatam.
  • Rebonjour,
    Dans l'exemple que tu prends: $x_1=x_2=x_3=x_4=x_5=x_7=1;\:\:\:x_6 =2\:\:$, $p=2$ , $q=3$ et l' algorithme annonce bien $354$ "mots" possibles.
    J' ignore ce qu'est un "programme en C" et ne peux donc expliquer pourquoi ton programme ne retourne pas $354$.
    Amicalement,
  • Re

    Alors je me suis trompé dans l'implémentation, je vais revoir mon code.

    Et l'algo fonctionne-t'il aussi s'il n-y a pas d'alias ?

    Encore merci pour tes réponses.

    Tatam.
  • Re,
    S'il n y a pas d' "alias", alors tous les $x_i$ sont égaux à $1$, et l'algorithme fonctionne parfaitement.
    Amicalement,

    PS Le nombre $54$ que tu obtiens peut s'expliquer par le fait qu'il correspond au nombre de codes contenant $2$ et seulement $2$ noms . L' erreur serait alors située à la fin de l'algorithme, dans le calcul de $N$.
  • Re.

    Mon calcul était bon, c'était un simple problème d'affichage "humain". Par exemple 1024 devient 1 024.
    Pour mon cas, j'ai mal calculé et 354 est devenu 54.

    Désolé d'avoir remis en question ton algo.

    Par ailleurs, j'ai fait les tests sans "alias" et c'est fonctionnel.

    Encore merci pour ton aide,
    Tatam.
  • re bonjour LOU16.

    Je me permets de faire suite à ce post car j'ai (encore ?) un nouveau problème sur mon programme.

    Le calcul pour lequel je t'ai sollicité est pour la prédiction dite "normal" de mon programme. Cependant, celui-ci peut générer des combinaisons avec altérations. Par exemple, en mettant la 1er lettre du mot concaténé en majuscule.

    C'est justement cette fonctionnalité qui me pose problème, encore une fois depuis que j'ai inclus les "alias".

    Voici un petit exemple de la liste initiale:
    alice|lili|lily
    bob
    1|01|janvier
    carole|caro
    dave
    fevrier|2|02

    La condition d'affichage de la concaténation est que le premier caractère soit compris entre 'a' et 'z'. Le mécanisme de génération reste le même, avec des intervalles etc.

    Les combinaisons suivantes sont donc possibles:
    Alice1
    Alice01
    Alice01bob
    etc.

    Les combinaisons suivantes sont impossibles:
    1Alice
    01Alice
    01Alicebob
    etc.

    Mon ancien calcul était simple:
    Je comptais le nombre de mots commençant pas [a-z] dans la liste initiale et je calculais le pourcentage de présence par rapport au total de mots.
    J'appliquais ce pourcentage sur le nombre total de mots généré en mode "normal" et j'obtenais mon résultat.

    Malheureusement, avec le système d'alias, cette méthode n'est plus possible.

    Peux-tu encore m'aider si cela ne te dérange pas ?

    Merci d'avance,
    Tatam.

    PS: Si avec mon nouveau problème je doit créer un nouveau poste, n'hésitez pas à me le signaler.
  • Bonjour tatam,

    Je n'ai pas compris de manière claire quelles étaient les nouvelle règles. Pour que j'y parvienne, peut-être le plus simple serait de me donner la liste de tous les "codes" obtenus avec par exemple $3$ ou $4$ personnes ayant chacune $1$, $2$ ou $3$ noms et $[2;3]$ pour intervalle de concaténation.
    Amicalement,
  • Re,

    Alors voici la liste initial:
    alice|lili
    bob
    janvier|1|01
    42

    Et voici tous les codes, avec l'altération de la 1er lettre en majuscule:
    Alicebob
    Bobalice
    Alicejanvier
    Janvieralice
    Alice1
    Alice01
    Alice42
    Lilibob
    Boblili
    Lilijanvier
    Janvierlili
    Lili1
    Lili01
    Lili42
    Bobjanvier
    Janvierbob
    Bob1
    Bob01
    Bob42
    Janvier42
    Alicebobjanvier
    Alicejanvierbob
    Bobalicejanvier
    Bobjanvieralice
    Janvierbobalice
    Janvieralicebob
    Alicebob1
    Alice1bob
    Bobalice1
    Bob1alice
    Alicebob01
    Alice01bob
    Bobalice01
    Bob01alice
    Alicebob42
    Alice42bob
    Bobalice42
    Bob42alice
    Alicejanvier42
    Alice42janvier
    Janvieralice42
    Janvier42alice
    Alice142
    Alice421
    Alice0142
    Alice4201
    Lilibobjanvier
    Lilijanvierbob
    Boblilijanvier
    Bobjanvierlili
    Janvierboblili
    Janvierlilibob
    Lilibob1
    Lili1bob
    Boblili1
    Bob1lili
    Lilibob01
    Lili01bob
    Boblili01
    Bob01lili
    Lilibob42
    Lili42bob
    Boblili42
    Bob42lili
    Lilijanvier42
    Lili42janvier
    Janvierlili42
    Janvier42lili
    Lili142
    Lili421
    Lili0142
    Lili4201
    Bobjanvier42
    Bob42janvier
    Janvierbob42
    Janvier42bob
    Bob142
    Bob421
    Bob0142
    Bob4201

    Resultat: 80

    Tatam.
  • J'appelle $N( x_1,x_2,...x_n, p ,q)$ le nombre de "codes" calculé par l'algorithme précédent et $\mathfrak N (x_1,x_2,...x_n,p,q)$ le nombre de codes possibles avec les nouvelles règles.
    Les choses commencent à devenir plus compliquées car d' autres paramètres doivent être pris en considération.
    J'appelle $t_i$ le nombre de noms "numériques" que possède la personne numérotée $i$. Ainsi le nombre $\mathfrak N$ cherché dépend aussi des $t_i$.
    Je donne dans le cas $n=3$ le calcul (que tu extrapoleras facilement lorsque $n$ est quelconque) qui permet d'accéder à $\mathfrak N(x_1,x_2,...x_n,p,q)$.
    $\mathfrak N (x_1,x_2,x_3, p, q)=N(x_1,x_2,x_3,p,q)- t_1N(x_2,x_3, p-1,q-1) -t_2 N(x_1,x_3,p-1,q-1) -t_3N (x_1,x_2,p-1,q-1)$
    Dans ton exemple: $x_1 =2 ,\: x_2 =1 \:,x_3 =3,\: x_4 = 1,\:\:\:$ $t_1=t_2=0,\: t_3 =2, \:t_4 =1\:\: $ et $\:p=2,\:q=3$.
    Alors $\mathfrak N(2,1,3,1,\:\: 2,3)= N(2,1,3,1,\:\:2,3) - 2\times N(2,1,1 ,\:\: 1,2)-1\times N(2,1,3,\:\: 1,2) = 136 -2\times 14-1\times 28= 80$.
    Le calcul de $\mathfrak N$ se ramène ainsi à plusieurs ($n$ au maximum si aucun $t_i$ n'est nul) calculs de $N$ qui relèvent de l'algorithme précédent.

    Amicalement,

    P.S. Pour résumer le calcul de $\mathfrak N$, disons que $\mathfrak N$ est égal au nombre de codes possibles avec les anciennes règles ($N$), diminué du nombre de ces codes commençant par un "nom numérique".
    $$\mathfrak N = N(x_1,x_2...x_n, p,q) - \sum_{i=1} ^{n} t_i N(x_1...x_{i-1},0, x_{i+1},...x_n,p-1,q-1)$$
  • Bonjour DOU16.

    Merci pour la réponse. Je n'ai pas encore eu le temps de me pencher sur tes équations mais je reviens vers toi dès que possible.

    Tatam.
  • Bonjour DOU16.

    Je viens de faire des essais et dans l'ensemble ça semble fonctionner à merveille, encore un grand merci !

    J'ai cependant quelques problèmes, notamment lorsque mon intervalle minimum (ici p) est égal à 1 (p=1). En effet, lorsque je calcule avec mes ti, p et q doivent êtres réduits de 1 par rapport à leurs valeurs initiales. Or, dans le cas ou p=1, celui-ci devient 0, se qui pose problème dans mon programme. Ai-je mal compris quelque chose ou y-a-t'il un cas particulier ?

    De plus, le calcule reste t'il le même lorsque les intervalles p et q changent ?

    Merci d'avance,
    Tatam.
  • Bonjour tatam,
    Lorsque $p=0$, le nombre $N_0$ qui intervient dans le calcul de $N=N_0 +N_1+...N_q$ est :$N_0 =1$.
    Amicalement,
  • Parfait, un problème persiste cependant.

    Lorsque q > 3 les prédictions de mon algo se révèlent fausses.

    Je donne pour exemple p=1, q=4
    Ma prédiction est de 192 (pour 168 mots générés).

    Autre exemple: p=4, q=4
    Prédiction: 108 (pour 84 mots générés).

    As-tu une idée sur le problème que je rencontre ? J'ai vérifié le résultat de ma génération et il semble bon.

    Je te link joins mon code si cela peux t'aider :
      unmatch = 0;
      array_unmatch = count_unmatch_first_maj(obj);
      array_alias = count_alias_per_word(obj);                                                                        
      for (k=1; k<=obj->nb_words; k++)
        {                                                              
          total = 0;
          array_coef = init_array_coef(obj);
          for (i=1; i<=obj->nb_words; i++)
            {
              for (j=0; j<=i; j++)
                {
                  if (k != i)
                    array_coef[i-j] += array_alias[ i] * array_coef[i-j-1];
                }                                            
            }                                          
          for (i=obj->min-1; i<=obj->max-1; i++)
            {
              if (i == 0)
                total += 1;
              else if (k != i)
                total += facto(i) * array_coef[ i];
            }
          unmatch += array_unmatch[k] * total;
        }
    
    Ici le nombre de "noms numériques" est unmatch.
    array_unmatch = ti initialisé au début.
    array_alias = xi initialisé au début.
    obj->min = p
    obj->max = q
    obj->nb_words = Nombre de nom (sans alias, juste les lignes de la liste initiale).
    facto() = Ma fonction de factorisation.

    Merci d'avance,
    Tatam.
  • Re
    Pour que je comprenne (peut-être), dans les exemples que tu as pris, l'origine de l'erreur, il te faut m'indiquer la valeur de tous les paramètres qui interviennent, c'est-à-dire, en dehors de $p$ et $q$, les valeurs des $x_i$ et des $t_i$.
    Amicalement,
  • Re.

    Oui bien sûr, ils valent comme dans les exemples plus haut:

    t = [0, 0, 0, 2, 1] où t3=2 et t4=1.

    x = [0, 2, 1, 3, 1] où x0=0, x1=2, x2=1, x3=3 et x4=1. Ici le premier mot est x1.

    Tatam.
  • Re,
    L' algorithme qui résulte du calcul que j'ai indiqué retourne des résultats conformes aux nombres de "mots" générés, à savoir: $168$ et $84$.
    Je t'indique "mon algorithme", qui utilise le précédent qui permettait d'obtenir $N(x_1,x_2...x_n,p,q)$ et qui, en sortie, fournit le nombre cherché dans la variable $S$.
    Entrer $p,\: q,\: x_1,\:x_2,\:....x_n,\:t_1,\:t_2,\:...t_n.$
    $S$ prend la valeur $N(x_1,x_2...x_n,p,q)$.
    Pour $i$ allant de $1$ à $n$,
    $\:\:\:\:\:\:X$ prend la valeur $x_i$.
    $\:\:\:\:\:\:x_i$ prend la valeur $0$.
    $\:\:\:\:\:\:S$ prend la valeur $S-\left(t_i\times N(x_1,x_2,...x_n,p-1,q-1)\right)$.
    $\:\:\:\:\:\:x_i$ prend la valeur $X$.
    Fin du Pour.
    Afficher $ S$.
    D'autre part , le calcul que je propose exige que dans une boucle "pour $i$ allant de $1$ à $n$", la variable $x_i$ soit "supprimée" ( ou comme dans mon cas remplacée par $0$) et cela ne m'apparait pas clairement dans ton code. Je n'y vois pas non plus une instruction contenant la soustraction que ma "formule" préconise, mais je ne comprends pas tout.

    Amicalement,
  • Bonjour LOU16.
    L' algorithme qui résulte du calcul que j'ai indiqué retourne des résultats conformes aux nombres de "mots" générés, à savoir: 168 et 84.
    Cela me rassure, ça veux simplement dire que mon implémentation est mal faite et que ma génération est bonne.
    D'autre part , le calcul que je propose exige que dans une boucle "pour i allant de 1 à n", la variable xi soit "supprimée" ( ou comme dans mon cas remplacée par 0) et cela ne m'apparait pas clairement dans ton code.
    Elle n'est pas clair mais elle y est:
              for (j=0; j<=i; j++)
                {
                  [b]if (k != i)[/b]
                    array_coef[i-j] += array_alias[ i] * array_coef[i-j-1];
                } 
    
    C'est le "if" en gras. On peut d'ailleurs le retrouver dans la boucle suivante:
          for (i=obj->min-1; i<=obj->max-1; i++)
            {
              if (i == 0)
                total += 1;
              [b]else if (k != i)[/b]
                total += facto(i) * array_coef[ i];
            }
    
    Je n'y vois pas non plus une instruction contenant la soustraction que ma "formule" préconise, mais je ne comprends pas tout.
    Je ne suis pas sur de comprendre, tu parles de la soustraction des "numériques" sur N ? Si c'est le cas, je le fait plus loin dans mon code. Je soustrait la variable unmatch à une variable qui se nomme num->nb_simple qui est obtenu pas le premier algo que tu m'a donné.

    Pour le nouvel algo, je ne l'ai pas encore essayer, je vais le faire ce soir et je te fait un retour.

    Tatam.

    PS: Désolé d'avoir écrit "Ici le premier mot est x1.", la vrai formule serait "Ici le premier ensemble de mot est x1.".
  • Re.

    J'ai trouvé.

    Le code suivant n'a pas l'effet que je pensais sur l'algo.
    if (k != i)
    

    J'ai donc opté pour ta solution qui est d'utiliser une variable temporaire (X dans ton exemple) pour pouvoir stocker xi et l'initialiser à 0.

    De nouveau, un grand merci pour ton aide, j'attaque le problème suivant.

    Tatam.
  • Bonjour.

    De nouveau, je suis bloqué pour prédire le nombre de combinaisons généré après une "altération".

    Pour le dernier calcul, la génération avait lieu si et seulement si le premier caractère de la concaténation était compris entre [a-z]. Si la condition était remplit, alors la 1er lettre devenait une majuscule.

    Cette fois, le problème est légèrement différent:
    La génération à lieu si et seulement si le premier caractère d'un des mots composant la concaténation est compris entre [a-z]. Si la condition est remplit, alors le premier caractère de chaque mots étant compris entre [a-z] devient une majuscule.

    Par exemple, les concaténations suivantes:
    alice + bob devient AliceBob
    lili + 01 devient Lili01
    42 + bob devient 42Bob
    42 + 1 ne sera pas généré

    Les "alias" sont toujours à prendre en comptes.

    Pour donner une base, voici la liste initiale:
    alice|lili
    bob
    janvier|1|01
    42

    Et voici la génération finale pour p=2 et q=3:
    AliceBob
    BobAlice
    AliceJanvier
    JanvierAlice
    Alice1
    1Alice
    Alice01
    01Alice
    Alice42
    42Alice
    LiliBob
    BobLili
    LiliJanvier
    JanvierLili
    Lili1
    1Lili
    Lili01
    01Lili
    Lili42
    42Lili
    BobJanvier
    JanvierBob
    Bob1
    1Bob
    Bob01
    01Bob
    Bob42
    42Bob
    Janvier42
    42Janvier
    AliceBobJanvier
    AliceJanvierBob
    BobAliceJanvier
    BobJanvierAlice
    JanvierBobAlice
    JanvierAliceBob
    AliceBob1
    Alice1Bob
    BobAlice1
    Bob1Alice
    1BobAlice
    1AliceBob
    AliceBob01
    Alice01Bob
    BobAlice01
    Bob01Alice
    01BobAlice
    01AliceBob
    AliceBob42
    Alice42Bob
    BobAlice42
    Bob42Alice
    42BobAlice
    42AliceBob
    AliceJanvier42
    Alice42Janvier
    JanvierAlice42
    Janvier42Alice
    42JanvierAlice
    42AliceJanvier
    Alice142
    Alice421
    1Alice42
    142Alice
    421Alice
    42Alice1
    Alice0142
    Alice4201
    01Alice42
    0142Alice
    4201Alice
    42Alice01
    LiliBobJanvier
    LiliJanvierBob
    BobLiliJanvier
    BobJanvierLili
    JanvierBobLili
    JanvierLiliBob
    LiliBob1
    Lili1Bob
    BobLili1
    Bob1Lili
    1BobLili
    1LiliBob
    LiliBob01
    Lili01Bob
    BobLili01
    Bob01Lili
    01BobLili
    01LiliBob
    LiliBob42
    Lili42Bob
    BobLili42
    Bob42Lili
    42BobLili
    42LiliBob
    LiliJanvier42
    Lili42Janvier
    JanvierLili42
    Janvier42Lili
    42JanvierLili
    42LiliJanvier
    Lili142
    Lili421
    1Lili42
    142Lili
    421Lili
    42Lili1
    Lili0142
    Lili4201
    01Lili42
    0142Lili
    4201Lili
    42Lili01
    BobJanvier42
    Bob42Janvier
    JanvierBob42
    Janvier42Bob
    42JanvierBob
    42BobJanvier
    Bob142
    Bob421
    1Bob42
    142Bob
    421Bob
    42Bob1
    Bob0142
    Bob4201
    01Bob42
    0142Bob
    4201Bob
    42Bob01

    Total: 132

    Je pensais pouvoir résoudre le problème seul grâce aux formules mathématiques vue plus haut, mais quelque chose m'échapper.

    Pourriez-vous me venir en aide ?

    Merci d'avance.

    Cordialement,
    Tatam.
  • Bonjour tatam,
    Il me semble que dans ce cas les choses soient assez simples. Avec mes notations antérieures, le nombre cherché est: $$\mathcal T = N(x_1,x_2,...x_n , p,q) -N(t_1,t_2,...t_n, p,q)$$.
    On soustrait au nombre de codes engendrés par les "premières règles" le nombre de codes exclusivement numériques.
    Dans l'exemple que tu prends, on a bien: $\mathcal T = 136 - 4 =132$.
    Amicalement,
  • Mais oui, je me sent si bête. Effectivement, se n'était pas bien compliqué compte tenu des formules précédentes.

    Merci beaucoup LOU16.

    Maintenant question final si possible:

    J'arrive (grâce à toi) à prédire l'ensemble des combinaisons quelque soit les altérations effectuées.

    J'aimerais maintenant prédire le poids final (en octet) d'une génération selon les options d'altérations et de l'intervalle p et q.

    Sachant qu'un caractère = 1 octet et un retour à la ligne = 1 octet.

    Par exemple, la liste initiale:
    alice|lili
    bob
    janvier|1|01
    42

    La génération sans altération pour p=1 et q=2:
    alice
    lili
    bob
    janvier
    1
    01
    42
    alicebob
    bobalice
    alicejanvier
    janvieralice
    alice1
    1alice
    alice01
    01alice
    alice42
    42alice
    lilibob
    boblili
    lilijanvier
    janvierlili
    lili1
    1lili
    lili01
    01lili
    lili42
    42lili
    bobjanvier
    janvierbob
    bob1
    1bob
    bob01
    01bob
    bob42
    42bob
    janvier42
    42janvier
    142
    421
    0142
    4201

    Poids = 295 octets

    Y a-t-il une formule capable de prédire cela ?
    Merci d'avance,
    Tatam.
  • Bonjour,

    Le nombre cherché est égal au nombre $N(x_1,x_2,\ldots,x_n,p,q)$ de "codes" déjà calculé, augmenté du nombre $\mathcal C$ de caractères utilisés. Il suffit donc de déterminer ce dernier.
    Le premier algorithme que je t'ai indiqué contient une boucle qui reçoit en entrée $x_1x_2,\ldots,x_n$ et retourne les coefficients polynomiaux $a_0=1, a_1, a_2,\ldots, a_n$ que je noterai $a_i( x_1,x_2,\ldots,x_n),\ (0\leq i\leq n)$ et que l'on utilisera dans ce qui suit.
    Le calcul de $\mathcal C$ dépend de $ x_1,x_2,\ldots,x_n , p,q$ , mais aussi de $s_1,s_2,\ldots,s_n$ où $s_i$ désigne la somme des nombres de caractères des "noms" que possède la personne numérotée $i$ (dans ton dernier exemple : $s_1 =9;\ s_2=3;\ s_3=10;\ s_4=2)$.
    L'algorithme suivant prend en entrée $x_1,x_2,\ldots,x_n, \ s_1,s_2,\ldots,s_n,\ p,q\ $ et produit le nombre cherché $\mathcal C$ dans la variable $C$.
    C  prend la valeur  0 .
    Pour  i  allant de  1  à  n 
        X  prend la valeur  x_i .
        x_i  prend la valeur  0 .
        S  prend la valeur  0 .
        Pour  k  allant de  p  à  q 
            S  prend la valeur  S+k! \times a_{k-1}(x_1,x_2,...x_n) 
        Fin du Pour.
        x_i   prend la valeur  X.
        C  prend la valeur  C+s_i \times S 
    Fin du Pour
    Afficher  C.
    
    Amicalement,
  • Bonjour LOU16.

    Merci pour ta réponse.

    Je ne comprends pas bien les "\times" dans ton algo ? Je pense que ce sont des balises LaTeX qui sot mal interprétées dans les balises de code formatées.

    Par ailleurs, somme nous bien d'accord que cet algo calcul le poids en octet d'un seul "type" de génération ? (soit normal, soit première lettre en majuscule, soit chaque majuscule).

    Merci d'avance,
    Tatam.
  • Bonjour,
    Désolé, mais la "modération du forum" a réécrit l'algorithme (qui devait donc contenir quelque chose d'excessif) que j'avais écrit, sous une forme apparemment moins lisible, et dans lequel "\times" n'apparaissait pas . Cela dit, "\ times" est le symbole LaTex de la multiplication.
    Cet algorithme calcule le nombre d'octets, seulement avec les "premières règles".
    Amicalement,
  • Bonjour LOU16.

    Je viens de faire un POC de ton algo et c'est fonctionnel, juste un petit oubli sur l'affichage final :
    Afficher  C + N
    
    Où N est égal au nombre total de lignes générées. Ici l'ajout de N correspond à chaque retour à la ligne.

    Il ne me reste plus qu'à intégrer cet algo dans mon code et aux fonctions "d'altération". Je te fais un retour quand ce sera fait.
    Encore merci,
    Tatam.
  • Bonjour.

    Je viens seulement d'implémenter la formule mathématique à mon code pour la prédiction du poids (en octet) dite "normal".

    Je pensais à tort que la formule serait la même pour les prédictions avec altérations, mais il n'en est rien. J'imagine que la formule doit simplement être adaptée mais je ne vois pas comment.

    Peux-tu m'éclairer LOU16 (ou quelqu'un d'autre) sur la prédiction du poids sur l'altération avec une majuscule sur la première lettre de la concaténation final ?

    Merci d'avance,
    Tatam.
  • Bonjour.

    Je me permets de re-poster un message afin de relancer la discussion de ce poste.

    Après quelques recherches et adaptations de l'algo de LOU16, je ne parviens toujours pas à prédire le "poids" de la génération lors de l'affichage avec la première lettre en majuscule.

    Quelqu'un peut-il me venir en aide ?

    Merci d'avance,
    Tatam.
  • Bonjour tatam,
    Les dénombrements que tu nous demandes d'effectuer sont de plus en plus complexes et deviennent (en tout cas pour
    moi) quasiment inextricables. Je ne touche pas au calcul du nombre $\mathcal K$ d'octets avec la "seconde règle".
    Avec la "troisième règle" , on peut faire: (avec les notations antérieures)
    $$ \mathcal K = \mathcal N(x_1,x_2,...x_n ,p,q) +\mathcal C(x_1,x_2,...x_n,s_1,s_2,...s_n,p,q) - \mathcal N(t_1,t_2,...t_n,p, q) - \mathcal C(t_1,t_2,...t_n,s_1',s_2',...s_n',p,q)$$
    où $s'_i$ est le nombre de caractères numériques contenus dans l' ensemble des noms de la personne numérotée $i$.
    Une remarque sans importance: il n'y avait pas d"oubli de ma part. J' avais écrit que l'algorithme indiqué était destiné à calculer $\mathcal C$.et non $\mathcal K =\mathcal C+\mathcal N$.
    Amicalement,
  • Bonjour LOU16.

    Merci pour ta réponse.

    Pour la "troisième règle" je vais essayer, je n'ai malheureusement pas beaucoup de temps en ce moment. Je te fait un retour dès que j'ai pu implémenter l'algo dans mon code.

    Pour la "deuxième règle", c'est dommage, je pense donc faire avec une estimation (un pourcentage de la première règle). Sinon, sais-tu vers qui je pourrais me tourner pour ce problème (s'il est solvable) ?

    Concernant le calcul de C pour la "première règle", désolé, j'ai encore mal compris tes propos, pardonne moi.

    Encore merci,
    Tatam.
  • Bonjour.

    Je ré-ouvre ce poste pour partager avec vous la publication de mon logiciel pour celles et ceux qui pourraient être intéressés:
    https://github.com/tatam/lama

    Cordialement,
    Tatam.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!