Constitution de chaine contenant toutes sous chaines de Tail

[philgsxr]

Bonjour,
dans un premier temps le pourquoi de la question :
N'ayant rien d'autre a faire je me suis retrouvé devant mon digicode, qui me demande quatre chiffres de 0 à 9 pour entrer....
à ce moment la je me demande le temps qu'il faut pour taper l'ensemble des combinaisons (soit 10 000 de 0000 à 9999) ou encore environ 4 heures à quelqu'un de très patient;
attendu que le digicode ne demande pas de validation (il suffit de sortir les 4 chiffres à la suite, peu importe ce qui a été fait avant) je me pose la question de l'existence d'une chaîne compacte contenant les 10000 combinaisons.

Les éléments que l'on a de manière immédiate sont les suivants :

Une chaîne comprenant toutes les combinaisons existe de manière triviale : il s'agit de
0000000100020003[.....].....999799989999 (longueur 4 x 10000 caractères)

La longueur minimale de chaîne est permettant d'extraire 10000 sous chaînes de taille 4 étant de 10003.
caractères (trivial).
Il existe des chaînes "équivalentes" dans les chaînes solution par permutation des caractères (trivial)

La question mathématique est donc la suivante : Peut on créer une chaîne de taille minimale (10003) contenant toutes les combinaisons possibles; sinon quelle est la taille de chaîne minimale garantissant l'existence en son sein de l'ensemble de combinaisons de 4 chiffres (avec nécessairement répétition de certain motifs)


quel algorithme de création ? par construction on par compression(ie identification de répétition de motifs et traitement) d'une solution connue

quelle formalisme adopter (ensemble des chaînes solutions, notion d' ordre des chaînes solution en fonction des répétitions de motif etc...)

Extension du probleme à des sous chaines de taille limitée mais variable - ou du nombre de symbole disponibles...
.....

voila c'était la réflexion du soir inspirée par ... mon tout bète digicode....

Pour autant le sujet est je pense assez ardu et s'approche des problèmes de crypto, force brute etc....

Merci d'avance....

[zygomatique]

salut

un sujet intéressant sur lequel il doit exister de la littérature je pense ....

et je pense qu'une telle chaine aura une longueur supérieure à 10003 ...

pour l'algorithme de création on peut remarquer qu'aucun chiffre ne doit se répéter plus de 4 fois ...

car si on a xxxxx alors on a les sous-chaines xxxx et xxxx en partant du premier x ou en partant du deuxième ...

ensuite je pense que pour toute sous-chaine abcd il faudra considérer la sous-chaines uvwabcdxyz qui conduit à sept sous-chaines de longueur 4 qui doivent non seulement être distinctes mais distinctes aussi des autres ....


voila qq idées ....