Bonjour à tous :)
C'est mon premier message donc pour ceux qui ne me connaissent pas (c'est à dire tous), je suis étudiant en master d'informatique à l'université de Brest. Désolé, je ne suis pas mathématicien, même si j'ai forcément étudié un peu le sujet (mais complètement rouillé...).
Mon problème est le suivant : je me suis demandé tout à l'heure s'il y avait une manière automatique d'obtenir la liste de toutes les combinaisons possibles de certains caractères.
Pour être plus précis, voilà un exemple : obtenir la liste de tous les octets. Jusque là vous me direz, pas de soucis. 00000000, puis 00000001, ..., 11111111.
Mais le résultat que je cherche serait plutôt de la forme 0000000011...
Comme ça en partant du caractère 0 j'aurais 0000000, en partant du 1 j'aurais 00000001, du 2 00000011, etc.
Personnellement je suis perdu, je ne vois pas comment obtenir un résultat optimal, mais je pense que c'est faisable avec des histoires de matrices et permutations... Peut-être :D
Du coup si quelqu'un a une idée ce serait cool ^^
Merci d'avance pour n'importe quelle piste !
Liste de toutes les combinaisons possibles d'un dictionnaire de caractères
16 messages
- Page 1 sur 1
Liste de toutes les combinaisons possibles d'un dictionnaire de caractères
par Saik » 25 Sep 2009, 16:48
par fatal_error » 25 Sep 2009, 18:19
salut,
je t'avouerai n'avoir rien compris avec ton exemple sur les octets.
00000000,00000001,?,11111111.
Quel est le nombre '?' : 000000010, ou bien 00000011, ou bien autre chose?
Que désigne le caractère 0, celui de droite?, une valeur d'un caractère?
Quel est le rapport entre le caractère 2 et l'octet 00000011
Enfin concernant la liste des combinaisons possibles des caractères de l'alphabet, il faut d'abord définir quelles sont les séquences autorisées (ou interdites) :
ex : un t ne suit pas un z. (jor zt)
Une fois que c'est fait, ca doit bien pouvoir se faire a coup dautomate et de classes je pense, im semble avoir lu un truc comme ca dans un vieux poly de premiere année.
je t'avouerai n'avoir rien compris avec ton exemple sur les octets.
Jusque là vous me direz, pas de soucis. 00000000, puis 00000001, ..., 11111111.
Mais le résultat que je cherche serait plutôt de la forme 0000000011...
Comme ça en partant du caractère 0 j'aurais 0000000, en partant du 1 j'aurais 00000001, du 2 00000011, etc.
00000000,00000001,?,11111111.
Quel est le nombre '?' : 000000010, ou bien 00000011, ou bien autre chose?
Que désigne le caractère 0, celui de droite?, une valeur d'un caractère?
Quel est le rapport entre le caractère 2 et l'octet 00000011
Enfin concernant la liste des combinaisons possibles des caractères de l'alphabet, il faut d'abord définir quelles sont les séquences autorisées (ou interdites) :
ex : un t ne suit pas un z. (jor zt)
Une fois que c'est fait, ca doit bien pouvoir se faire a coup dautomate et de classes je pense, im semble avoir lu un truc comme ca dans un vieux poly de premiere année.
la vie est une fête 
par Saik » 25 Sep 2009, 18:45
Salut
entre 00000001 et 11111111 il y a toutes les combinaisons binaires correspondant aux chiffres 2 à 254. Mais ce n'est qu'un exemple.
Quand je parle du caractère 0, je veux dire le premier de la liste, puis en partant du deuxième (sur 8 caractères comme il s'agit d'un octet, etc). J'ai l'habitude de commencer à 0, j'aurais peut-être du dire "caractère 1" ^^'
entre 00000001 et 11111111 il y a toutes les combinaisons binaires correspondant aux chiffres 2 à 254. Mais ce n'est qu'un exemple.
Quand je parle du caractère 0, je veux dire le premier de la liste, puis en partant du deuxième (sur 8 caractères comme il s'agit d'un octet, etc). J'ai l'habitude de commencer à 0, j'aurais peut-être du dire "caractère 1" ^^'
par fatal_error » 25 Sep 2009, 19:03
re Finrod,
en fait je pense que Saik's desire ( :we: ) is to count tous les mots potentiellement formables avec un certain nombre de lettres.
D'un point de vue basique, on peut faire avec des mots de n caracteres (26)^n mots possibles. ( le caractere représente une lettre quelconque parmi les 26 lettres de l'alphabet).
Mais comme je disais avant il y a des mots qu'on peut enlever parce qu'on sait qu'ils seront jamais corrects.
en fait je pense que Saik's desire ( :we: ) is to count tous les mots potentiellement formables avec un certain nombre de lettres.
D'un point de vue basique, on peut faire avec des mots de n caracteres (26)^n mots possibles. ( le caractere représente une lettre quelconque parmi les 26 lettres de l'alphabet).
Mais comme je disais avant il y a des mots qu'on peut enlever parce qu'on sait qu'ils seront jamais corrects.
la vie est une fête
par Saik » 25 Sep 2009, 20:38
Euh...
Non ce n'est pas ça en fait ^^' J'ai du mal expliquer le problème, désolé.
En fait je cherche une chaine de caractères, une suite de symboles si vous préférez, comprenant toutes les combinaisons possibles avec les symboles que j'ai au départ.
Pour faire un exemple complet, disons que je veux toutes les combinaisons de a et b d'une longueur de 2. J'ai donc :
aa
ab
ba
bb
et la chaine "aababb" contient toutes ces combinaisons (mais avec la combinaison ab en double, ce que j'aimerais éviter). (edit : la solution optimale étant ici "aabba" si je ne m'abuse...)
Non ce n'est pas ça en fait ^^' J'ai du mal expliquer le problème, désolé.
En fait je cherche une chaine de caractères, une suite de symboles si vous préférez, comprenant toutes les combinaisons possibles avec les symboles que j'ai au départ.
Pour faire un exemple complet, disons que je veux toutes les combinaisons de a et b d'une longueur de 2. J'ai donc :
aa
ab
ba
bb
et la chaine "aababb" contient toutes ces combinaisons (mais avec la combinaison ab en double, ce que j'aimerais éviter). (edit : la solution optimale étant ici "aabba" si je ne m'abuse...)
par Finrod » 25 Sep 2009, 20:52
aabba est une solution optimale mais elle n'est pas unique non ?
bbaab est optimale
abbaa aussi
baabb aussi
après si j'ai compris ce coup ci , la résolution dépend fortement des données de départ. Il y a peut être une formule qui en fonction du nombre de lettres, du nombre de lettre par caractère de base et du nombre de caractère de base, te donnera la longueur de ta solution, mais elle a pas l'air simple.
bbaab est optimale
abbaa aussi
baabb aussi
après si j'ai compris ce coup ci , la résolution dépend fortement des données de départ. Il y a peut être une formule qui en fonction du nombre de lettres, du nombre de lettre par caractère de base et du nombre de caractère de base, te donnera la longueur de ta solution, mais elle a pas l'air simple.
par Saik » 25 Sep 2009, 21:05
Finrod a écrit:Il y a peut être une formule qui en fonction du nombre de lettres, du nombre de lettre par caractère de base et du nombre de caractère de base, te donnera la longueur de ta solution, mais elle a pas l'air simple.
C'est bien ça mon problème ^^'
par fatal_error » 25 Sep 2009, 21:12
ah ok!
j'étais plutot loin du compte :cry:
La comme ca, ca me fait penser au compte est bon.
Le truc de base, c'est de générer les mots possibles.
Mettons qu'on en ait n.
On en accolle 2. Et on regarde si ca engendre des mots qui existent deja. Si c'est le cas, on les enleve de la liste des mots a accoller.
En outre, on fait une liste des mots utilisés.
Si parmi tous les mots que ca génère il y en a deja un dans la liste des mots utilisés, alors ca invalide l'essai. On accole alors deux autres mots.
Sinon, ben on continue jusqu'a ce que la liste des mots a générer soit vide.
Bon, ca c'est lourd, donc ya surement des criteres darret pour gagner du temps.
par exemple : on peut utiliser la symetrie.
cad :
si aababb est solution, alors bbabaa aussi, et de manière plus générale, toute les permutations de lettres.
Du coup, d'un point de vu algorithmique, ca pourrait se traduire par
le premier mot qu'on accolle commence obligatoirement par la lettre a.
Et on cherche toutes les solutions qui decoulent des mots qui commencent par a.
Pis apres on pourra permutter les lettres.
Une question qui se pose : est-ce qu'il n'y a qu'une seule solution? 0 solution?.
Par contre, c'est gros en espace mémoire.
j'étais plutot loin du compte :cry:
La comme ca, ca me fait penser au compte est bon.
Le truc de base, c'est de générer les mots possibles.
Mettons qu'on en ait n.
On en accolle 2. Et on regarde si ca engendre des mots qui existent deja. Si c'est le cas, on les enleve de la liste des mots a accoller.
En outre, on fait une liste des mots utilisés.
Si parmi tous les mots que ca génère il y en a deja un dans la liste des mots utilisés, alors ca invalide l'essai. On accole alors deux autres mots.
Sinon, ben on continue jusqu'a ce que la liste des mots a générer soit vide.
Bon, ca c'est lourd, donc ya surement des criteres darret pour gagner du temps.
par exemple : on peut utiliser la symetrie.
cad :
si aababb est solution, alors bbabaa aussi, et de manière plus générale, toute les permutations de lettres.
Du coup, d'un point de vu algorithmique, ca pourrait se traduire par
le premier mot qu'on accolle commence obligatoirement par la lettre a.
Et on cherche toutes les solutions qui decoulent des mots qui commencent par a.
Pis apres on pourra permutter les lettres.
Une question qui se pose : est-ce qu'il n'y a qu'une seule solution? 0 solution?.
Par contre, c'est gros en espace mémoire.
la vie est une fête
par Finrod » 25 Sep 2009, 21:14
J'ai peut être un idéee, je reviens l'érire (je fais de la puréé en même temps,l'eau bout...)
ça y est.
Bon : tu prend n lettres et des mots de longueur p comme caractère de base. ça te fait donc n^{p} caractères de bases.
Idée : tu peux les regarder à permutation circulaire prés. Tous les caractére d'une classe d'équivalence à permutation circulaire prés peuvent être écrit avec une chaine de 2p-1 lettres.
je crois que j'ai raté ma purée entre temps...
Bon alors après, il faut regarder le groupe des permutations de p éléments et vérifier ce qu'il manque comme générateur quand ona déjà les p-cycles.
ça y est.
Bon : tu prend n lettres et des mots de longueur p comme caractère de base. ça te fait donc n^{p} caractères de bases.
Idée : tu peux les regarder à permutation circulaire prés. Tous les caractére d'une classe d'équivalence à permutation circulaire prés peuvent être écrit avec une chaine de 2p-1 lettres.
je crois que j'ai raté ma purée entre temps...
Bon alors après, il faut regarder le groupe des permutations de p éléments et vérifier ce qu'il manque comme générateur quand ona déjà les p-cycles.
par Saik » 25 Sep 2009, 21:18
fatal_error a écrit:Une question qui se pose : est-ce qu'il n'y a qu'une seule solution? 0 solution?.
Il y a forcément au moins une solution, cad la succession de tous les motifs.
La place mémoire ne me pose pas spécialement de problème. (même si évidemment je préfère réussir à obtenir une solution optimale ^^')
edit : bon ap' ^^
par Finrod » 25 Sep 2009, 21:55
Je ne vois pas comment faire dans le cas le plus général.
Je n'ai que le cas particulier des cycles.
Je n'ai que le cas particulier des cycles.
par Doraki » 26 Sep 2009, 08:03
Ca ne me surprendrait pas si il y a un moyen d'avoir une seule et unique occurence de chaque mot.
Faudrait que je teste plus mais il me semble que ça marche pour un alphabet à deux lettres.
Faudrait que je teste plus mais il me semble que ça marche pour un alphabet à deux lettres.
par Finrod » 26 Sep 2009, 08:31
Oui mais pas à plus.
A deux lettres, il n'y a que des "p-cycles" et c'est équivalent à ce que j'ai dit hier.
dés qu'il y a plus de lettres, c'est l'angoisse.
Ce qui serait intéressant aussi, c'est de quoi Saik a besoin exactement et pour quelle raison ^^
encore qu'avec trois lettres et des mots de longueur 3, tu as 6 mots à 3 lettres distinctes (abc-bca-cab) sont dans la même classe vis à vis des 3-cycles, de même que (acb-cba-bac)
Après, il y a les mots sans a : (cbb-bbc-bcb)(bcc-ccb-cbc) deux classes pour les 3 cycles aussi.
Plus deux classes pour les sans b et les sans c.
Plus les trois mots aaa, bbb, ccc.
Pour le mot solution, il faut compter 2p-1 soit 3+2 par classe (par ex, pour la première classe abc-bca-cab: abcab): 5x8 classes plus trois mots aaa, bbb, ccc. Comme jesuis optimiste, je pense qu'on peut réduire à chaque accollement de classe de 1, il y a dix accollement, on peut donc sans doute réduire de 10.
ce qui ferait 49-10 = 39 pour la longueur de la solution.
Bon on peut réduire réduire plus les accollement.
ex abcab que l'on accole à abbab (cycle abb-bba-bab) puis à abaab (cycle aba-baa-aab)
Du coup,sur les 8 cycles, on peut en mettre (abc-bca-cab) avec les sans c pour un cout en longueur de 11, puis de même les (acb-cba-bac) avec les sans b pour un cout de 11
on peut coller les deux "sans a" pour faire un mot de 8.
Une proposition de mot solution je met des tiré pour les recollements
abcabbabaab (11) + acbaccacaac (11) + bccbcbbc (8) + aaa + bbb + ccc
On aurait abcabbabaab - b - bccbcbbc - cc - aa - acbaccacaac soit 29.
A deux lettres, il n'y a que des "p-cycles" et c'est équivalent à ce que j'ai dit hier.
dés qu'il y a plus de lettres, c'est l'angoisse.
Ce qui serait intéressant aussi, c'est de quoi Saik a besoin exactement et pour quelle raison ^^
encore qu'avec trois lettres et des mots de longueur 3, tu as 6 mots à 3 lettres distinctes (abc-bca-cab) sont dans la même classe vis à vis des 3-cycles, de même que (acb-cba-bac)
Après, il y a les mots sans a : (cbb-bbc-bcb)(bcc-ccb-cbc) deux classes pour les 3 cycles aussi.
Plus deux classes pour les sans b et les sans c.
Plus les trois mots aaa, bbb, ccc.
Pour le mot solution, il faut compter 2p-1 soit 3+2 par classe (par ex, pour la première classe abc-bca-cab: abcab): 5x8 classes plus trois mots aaa, bbb, ccc. Comme jesuis optimiste, je pense qu'on peut réduire à chaque accollement de classe de 1, il y a dix accollement, on peut donc sans doute réduire de 10.
ce qui ferait 49-10 = 39 pour la longueur de la solution.
Bon on peut réduire réduire plus les accollement.
ex abcab que l'on accole à abbab (cycle abb-bba-bab) puis à abaab (cycle aba-baa-aab)
Du coup,sur les 8 cycles, on peut en mettre (abc-bca-cab) avec les sans c pour un cout en longueur de 11, puis de même les (acb-cba-bac) avec les sans b pour un cout de 11
on peut coller les deux "sans a" pour faire un mot de 8.
Une proposition de mot solution je met des tiré pour les recollements
abcabbabaab (11) + acbaccacaac (11) + bccbcbbc (8) + aaa + bbb + ccc
On aurait abcabbabaab - b - bccbcbbc - cc - aa - acbaccacaac soit 29.
par Doraki » 27 Sep 2009, 14:33
aaababbbaacbacabcbbcaccbcccaa contient exactement 1 fois tous les mots de 3 lettres.
16 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 6 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :