Calcul combinaison avec exception/alias

tatam · March 2018

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.

LOU16 · March 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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 X⁴+7X³+17X²+17X+6. X⁴ pour le premier intervalle, 7X³ 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.

LOU16 · April 2018

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

tatam · April 2018

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.

LOU16 · April 2018

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

tatam · April 2018

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:
a_i-k prend la valeur a_i-k + (x_i x a_i-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.

LOU16 · April 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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

tatam · April 2018

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.

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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

tatam · April 2018

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.

tatam · April 2018

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 t_i, 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.

LOU16 · April 2018

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,

tatam · April 2018

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 = t_i initialisé au début.
array_alias = x_i 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.

LOU16 · April 2018

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,

tatam · April 2018

Re.

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

t = [0, 0, 0, 2, 1] où t₃=2 et t₄=1.

x = [0, 2, 1, 3, 1] où x₀=0, x₁=2, x₂=1, x₃=3 et x₄=1. Ici le premier mot est x₁.

Tatam.

LOU16 · April 2018

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,

tatam · April 2018

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 x₁.", la vrai formule serait "Ici le premier ensemble de mot est x₁.".

tatam · April 2018

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 x_i et l'initialiser à 0.

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

Tatam.

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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.

LOU16 · April 2018

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,

tatam · April 2018

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.

tatam · April 2018

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.

tatam · May 2018

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.

LOU16 · May 2018

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,

tatam · May 2018

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.

tatam · June 2018

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.

Calcul combinaison avec exception/alias

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 13