Compter le nombre de chaînes
Bonjour à tous,
j'ai un problème à résoudre mais je ne sais comment m'y prendre.
Je dois estimer le nombre de chaînes de 8 caractères alphanumériques possible...
Jusque la tout va bien, c'est 36^8
Mais j'ai une contrainte supplémentaire : les chaînes doivent avoir au moins 2 caractères différents entre elles. Pardonnez mon usage des notations mathématiques qui sera sans doute approximatif :
- je considère xn et yp pouvant prendre les valeurs [0,1,2,...,36]
- je considère les chaines (x1,x2,x3,x4,x5,x6,x7,x8) et (y1,y2,y3,y4,y5,y6,y7,y8)
Si (x1 = y1) et (x2 = y2) et (x3 = y3) et (x4 = y4) et (x5 = y5) et (x6 = y6)
Alors, je dois obligatoirement avoir (x7 <> y7) et (x8 <> y8)
EDIT : merci à GaBuZoMeu qui a reformulé mon problème de manière intelligible :
Quel est le nombre maximal d'éléments d'un ensemble A de chaînes de caractères de longueur 8 (sur un alphabet de 36 caractères) tel que deux éléments distincts de A diffèrent toujours en au moins deux places ?
Pourriez-vous m'aider à calculer ce nombre et à comprendre la méthodologie employée s'il vous plaît ? Mes connaissances en combinatoire et dénombrement sont plus que maigres et datent de plus de 10 ans...
Merci d'avance pour votre aide précieuse.
Kill
j'ai un problème à résoudre mais je ne sais comment m'y prendre.
Je dois estimer le nombre de chaînes de 8 caractères alphanumériques possible...
Jusque la tout va bien, c'est 36^8
Mais j'ai une contrainte supplémentaire : les chaînes doivent avoir au moins 2 caractères différents entre elles. Pardonnez mon usage des notations mathématiques qui sera sans doute approximatif :
- je considère xn et yp pouvant prendre les valeurs [0,1,2,...,36]
- je considère les chaines (x1,x2,x3,x4,x5,x6,x7,x8) et (y1,y2,y3,y4,y5,y6,y7,y8)
Si (x1 = y1) et (x2 = y2) et (x3 = y3) et (x4 = y4) et (x5 = y5) et (x6 = y6)
Alors, je dois obligatoirement avoir (x7 <> y7) et (x8 <> y8)
EDIT : merci à GaBuZoMeu qui a reformulé mon problème de manière intelligible :
Quel est le nombre maximal d'éléments d'un ensemble A de chaînes de caractères de longueur 8 (sur un alphabet de 36 caractères) tel que deux éléments distincts de A diffèrent toujours en au moins deux places ?
Pourriez-vous m'aider à calculer ce nombre et à comprendre la méthodologie employée s'il vous plaît ? Mes connaissances en combinatoire et dénombrement sont plus que maigres et datent de plus de 10 ans...
Merci d'avance pour votre aide précieuse.
Kill
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je me rend compte que j'ai mal exprimé ma condition. Effectivement, si je devais juste retirer est chaines faites d'un unique caractère, c'aurait été trop simple.
J'essaie de modéliser le problème et je l'ajoute dans mon premier poste. pardonnez mon usage des notations mathématiques qui sera sans doute approximatif :
- je considère xn et yp pouvant prendre les valeurs [0,1,2,...,36]
- je considère les chaines (x1,x2,x3,x4,x5,x6,x7,x8) et (y1,y2,y3,y4,y5,y6,y7,y8)
Si (x1 = y1) et (x2 = y2) et (x3 = y3) et (x4 = y4) et (x5 = y5) et (x6 = y6)
Alors, je dois obligatoirement avoir (x7 <> y7) et (x8 <> y8)
mais ça pourrait etre les 2 premiers termes qui soient différents entre eux, oubien le premier et le 6ème etc...
par ailleurs, comment faire pour insérer les caractères spéciaux comme le "=" barré ? quand je publie le message, il le remplace par un "?"
Tu dis vouloir compter les chaînes de caractères possédant une certaine propriété. Laquelle ?
Est-ce qu'il faut comprendre ce que tu racontes comme ça :
On se donne une chaîne de longueur 8. On veut compter toutes les chaînes de caractères qui diffèrent de la chaîne donnée en au moins deux places.
Ou alors, ton problème n'est pas de compter les chaînes de caractères possédant une certaine propriété, mais un problème du genre : quelle est le plus grand nombre d'éléments possible pour un ensemble de chaînes dans lequel deux chaînes distinctes quelconques diffèrent en au moins deux places ?
Compter les chaînes de caractères possédant une certaine propriété, mais un problème du genre : quelle est le plus grand nombre d'éléments possible pour un ensemble de chaînes dans lequel deux chaînes distinctes quelconques diffèrent en au moins deux places ?
Ton problème est bien :
Quel est le nombre maximal d'éléments d'un ensemble $A$ de chaînes de caractères de longueur 8 (sur un alphabet de 36 caractères) tel que deux éléments distincts de $A$ diffèrent toujours en au moins deux places ?
Réponds oui ou non, comme ça on saura à quoi s'en tenir.
Recherche 'cle de controle code barre EAN13' pour avoir l'explication
Exemple de formule : $n_8 = mod ( n_1 +n_2 +n_3 + n_4 + n_5 + n_6 + n_7,36) $
Prenons 2 chaines différentes.
Soit il y a déjà au moins 2 caractères qui sont différents dans les 7 premières positions, et ces chaines conviennent.
Soit il y a un seul caractère qui les différencie dans les 7 premières positions, et alors le 8ème caractère donné par cette formule sera forcément différent.
On a donc l'assurance que toutes les chaines construites ainsi prises 2 à 2 ont au moins 2 caractères différents.
Soit $N$ le cardinal d'un ensemble $A$ de chaînes tel que deux d'entre elles diffèrent toujours au moins en deux places. On a l'habitude d'appeler "distance de Hamming" entre deux chaînes de même longueur le nombre de places où elles différent. La distance non nulle minimale dans $A$ est supérieure ou égale à 2.
Comptons le nombre de paires $\{c,d\}$ où $c$ est dans $A$, $d$ n'est pas dans $A$, et la distance de $c$ à $d$ est 1.
Pour chaque $c$ dans $A$, aucun de ses $8\times 35$ voisins à distance 1 n'est dans $A$. Il y a donc $N\times 8\times 35$ telles paires.
Pour chaque $d$ qui n'est pas dans $A$, et pour chaque place de $d$, il y a au plus un élément de $A$ qui diffère de $d$ seulement en cette place. Le nombre de paires est donc majoré par $(36^8-N)\times 8$.
On en déduit $N\leq 36^7$. Le système du bit de parité réalise donc bien le maximum.
C'est d'ailleurs valable quel que soit la longueur des chaînes, et quel que soit le nombre de caractères dans l'alphabet.
Je vais essayer de comprendre comment est calculé le caractère de contrôle et pourquoi il sera forcément différent.
Je comprends qu'il existe un unique caractère répondant aux règles de calcul avec les 7 premiers caractères en inputs, mais je veux comprendre pourquoi !
On est exactement dans la même logique, et l'unicité est évidente.
Le gencod, c'est un code sur 13 chiffres. En fait 12 chiffres plus un caractère de contrôle.
Quand on a choisi les 12 premiers chiffres, on fait une certaine opération. Pour simplifier, je vais dire qu'on additionne ces 12 chiffres (ce n'est pas tout à fait ça, mais peu importe) ça nous donne un résultat.
Par exemple, si les 12 premiers chiffres sont 302010111111, la somme donne 12.
Dans le cas du gencod, on part de ce nombre, et on prend le complément à la dizaine supérieure. ici, 20-12, ça donne 8. Et donc le 13 ème chiffre sera 8, obligatoirement.
L'unicité est garantie (on additionne nos 12 chiffres, si on obtient 12 ou 22 ou 32 ou 42 ou ... , alors on ajoute un 8 ; si on obtient 13 ou 23 ou 3 ou 43 ..., on ajoute un 7, etc etc )
Dans ton cas, c'est exactement pareil.
Attention quand même. Je dis qu'à partir des 12 premiers chiffres , on les additionne... puis on cherche le complément à la dizaine supérieure... ok, cette méthode marche.
Dans la vraie méthode du gencod, on prend certains chiffres, on les additionne. On multiplie ce résultat par 3. Puis on additionne tous les autres chiffres.
Dans le cas du gencod, ça marche. Ca assure que 2 gencods différents ont bien au moins 2 chiffres différents.
Dans ton cas, ça ne marcherait pas !
Je te dirais bien de deviner pourquoi ... mais je pense que tu vas galérer... oublie le challenge. C'est sans importance.
Par contre, dans ton cas, considérer que chacun des 7 premiers caractères est un nombre entre 0 et 35, additionner ces 7 nombres, et garder ce resultat (modulo 35), ça marche.