MathemaTeX

Forum francophone relatif aux Mathématiques avec support LaTeX et Asymptote.
http://forum.mathematex.net/

Permutation, transposition, ...

http://forum.mathematex.net/asymptote-f34/permutation-transposition-t12730.html

Page 1 sur 1

Permutation, transposition, ...

MessagePosté: Jeudi 24 Mars 2011, 12:42
par maurice
Bonjour, je cherche à écrire les lettres de l'alphabet dans un ordre aléatoire ; voici le code :

1ff5ce27f3ed313568f823771ea5fc56.png

Code: Tout sélectionner
unitsize(0.5cm);

string[] alph={"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

void aff(int j=0, string[] T) {
for(int k=0; k<26; ++k) {
label(T[k], (k,j), N);
}
}

string[] trans(string[] T, int i, int j) {
string[] T1=T;
string s=T1[i];
T1[i]=T1[j];
T1[j]=s;
return T1;
}


string[] permut(int n=26, string[] T) {
string[] T2=T;
for (int k=0; k<n; ++k) {
int j;
j=floor(k*unitrand());
if (j != k) {trans(T2, k, j);}
}
return T2;
}

aff(0,alph);
aff(-1,trans(alph, 0,1));
aff(-2,alph);
aff(-4,permut(alph));
aff(-5,alph);


Ma question est de savoir
1) peut être il existe des fonction déjà définies pour les transposition, permutation, permutation aléatoire, ...
2) Pourquoi, alors qu'il y a return T1; ou return T2, la liste string[] T est modifiée dans chaque cas (les 3e et 5e lignes devraient être les mêmes que la 1ère).
Autrement dit, comment faire pour que alph reste toujours égale à :
Code: Tout sélectionner
string[] alph={"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

dans cet ordre.

Merci d'avance

Maurice

Re: permutation, transposition, ...

MessagePosté: Jeudi 24 Mars 2011, 14:10
par maurice
C'est mieux comme ça, grâce aux infos trouvées sur le site de Gaétan.

a9f8f705a2e29b0b875ed13645017323.png

Code: Tout sélectionner
unitsize(0.5cm);

string[] alph={"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

void aff(int j=0, string[] T) {
for(int k=0; k<26; ++k) {
label(T[k], (k,j), N);
}
}

string[] trans(string[] T, int i, int j) {
string[] T1=new string[T.length];
for (int k=0; k<T.length; ++k) {
if (k!=i && k!=j) T1[k]=T[k];
else {
if(k==i) T1[i]=T[j];
else T1[j]=T[i];
}
}
return T1;
}


string[] permutalea(string[] T) {
string[] T2=new string[T.length];
for (int k=0; k<T.length; ++k) T2[k]=T[k];
for (int k=0; k<T.length; ++k) {
int j;
j=floor(k*unitrand());
if (j != k) {T2=trans(T2, k, j);}
}
return T2;
}

aff(0,alph);
aff(-1,trans(alph, 0,5));
aff(-2,alph);
aff(-4,permutalea(alph));
aff(-5,alph);


Il reste la première question : pas de fonctions de ce type prédéfinies ?

Maurice

Re: permutation, transposition, ...

MessagePosté: Jeudi 24 Mars 2011, 21:07
par OG
maurice a écrit:Il reste la première question : pas de fonctions de ce type prédéfinies ?

pas à ma connaissance.


O.G.

Re: permutation, transposition, ...

MessagePosté: Jeudi 24 Mars 2011, 22:21
par GMaths
N'est ce pas plus simple avec un simple "string" et des fonctions de chaines pour en extraire des parties ?

Il me semble que oui :

d48377e83e90a00163791b382cb44f51.png

Code: Tout sélectionner
unitsize(.5cm);

string alph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int y=0;

void melangeons(string chaine, pair p){
int nbr=length(chaine), j;
string motmelange;
while(nbr>0) {
nbr=length(chaine);
j=floor(nbr*unitrand());
motmelange=motmelange+substr(chaine,j,1);
chaine=substr(chaine,0,j)+substr(chaine,j+1,nbr);
}
label(motmelange,p);
}
label(alph,(0,y));
melangeons(alph,(0,--y));
melangeons(alph,(0,--y));
melangeons(alph,(0,--y));
melangeons(alph,(0,--y));
melangeons(alph,(0,--y));

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 07:50
par maurice
GMaths a écrit:N'est ce pas plus simple avec un simple "string" et des fonctions de chaines pour en extraire des parties ?


Sans doute que si ! J'avais commencé à le découvrir un peu tout seul ! j'ai écris le début du code avec mes petites connaissances sur les string quasi-nulls et ai découvert à fur et à mesure les commandes du type substr, erase, insert, find, ...

Je pense donc me repencher sur le problème.

Maurice

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 16:29
par maurice
Bonjour,
voila où j'en suis avec un résultat bizarre :

b62c55a594dd37f8f34915734e8fd45c.png

Code: Tout sélectionner
unitsize(0.5cm);

string alph="ABCDEFGHI";



/* AFFICHER UN ALPHABET AVEC UN DECALAGE DE n (CESAR) SUR LA LIGNE D'ORDONNEE j */

void affiche(int n=0, string T, int j=0) {
for(int k=0; k<length(T); ++k) {
label(substr(T, pos=(k-n)%length(T), n=1), (k,j), N);
}
}


/* ECHANGE DEUX LETTRES DE L'ALPHABET (i!=j)*/

string trans(string T, int i, int j) {
string s1=substr(T,i-1,1);
string s2=substr(T,j-1,1);
string T1;
if (i==j) T1=T;
else {
if (i<j) {T1=substr(T,0,i-1)+s2+substr(T,i,j-i-1)+s1+substr(T,j,-1);}
else {T1=substr(T,0,j-1)+s1+substr(T,j,i-j-1)+s2+substr(T,i,-1);}
}
return T1;
}




/* PERMUTATION ALEATOIRE DE LA CHAINE DE CARACTERE T */


void permut_alea(string T) {
string T2=T;
for (int k=0; k<length(T); ++k) {
int j;
j=floor(k*unitrand()+1);
if (j != k) T2=trans(T2, j, k);
affiche(T2,-k);
}
//return T2;
}


permut_alea(alph);


Pourquoi la chaîne alph s'affiche deux fois ?
J'avoue je sèche, c'est ça de pas avoir fait d'info dans sa jeunesse !

Merci

Maurice

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 17:22
par maurice
Bonjour, en remplaçant trans par :

Code: Tout sélectionner
string transposer(string T, int i, int j) {
      string s1=substr(T,i,1);
      string s2=substr(T,j,1);
      string T1=T;
      if (j==length(T)-1) {
         T1=erase(T1, i, 1);
         T1=insert(T1, i, s2);
         T1=erase(T1, j, 1);
         T1=T1+s1;
      }
      else {
         T1=erase(T1, i, 1);
         T1=insert(T1, i, s2);
         T1=erase(T1, j, 1);
         T1=insert(T1,j,s1);
      }
   return T1;
}


CA travaille mieux, mais j'aimerais bien comprendre l'erreur précédent (ces histoires d'indices qui deviennent négatifs ....!)

Maurice

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 17:30
par GMaths
Je ne peux pas tester car je ne suis pas chez moi : je le ferai dans une heure.

Mais j'ai une question préalable : que cherches-tu à faire ?

Toujours à mélanger les lettres d'un mot ? Si oui, ma solution ne t'allait pas ?
Si non... ce serait plus facile de t'aider, en sachant précisément le cahier des charges de ce que tu veux.

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 17:54
par maurice
GMaths a écrit:Mais j'ai une question préalable : que cherches-tu à faire ?


Je prépare un cours sur la cryptographie (code de césar, chiffre de Vigenère, ...) et essai de faire des algorithmes pour chiffrer/déchiffrer avec asymptote.

fda8bb6c88dd074d12b9b7a75f70726c.png

Code: Tout sélectionner
unitsize(0.5cm);

string[] alph={"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};

void cesar(int n=0, string[] T, int j=0) {
for(int k=0; k<26; ++k) {
label(T[(k-n)%26], (k,j), N);
}
}

string[] trans(string[] T, int i, int j) {
string[] T1=new string[T.length];
for (int k=0; k<T.length; ++k) {
if (k!=i && k!=j) T1[k]=T[k];
else {
if(k==i) T1[i]=T[j];
else T1[j]=T[i];
}
}
return T1;
}


string[] permutalea(string[] T) {
string[] T2=new string[T.length];
for (int k=0; k<T.length; ++k) T2[k]=T[k];
for (int k=0; k<T.length; ++k) {
int j;
j=floor(k*unitrand());
if (j != k) {T2=trans(T2, k, j);}
}
return T2;
}


void tableau_de_substitution(int n=0) {
label("\textbf{Texte clair}", (-6.5,n+0.5), E);
label("\textbf{Texte chiffr\'e}", (-6.5,n-0.5), E);
draw((-6.5,n+1)--(25.5,n+1));
draw((-6.5,n)--(25.5,n));
draw((-6.5,n-1)--(25.5,n-1));
draw((-6.5,n-1)--(-6.5,n+1));
for (int k=0; k<=26; ++k) draw((k-0.5,n-1)--(k-0.5,n+1));
}


string codemonoalph(string s, string[] alph, string[] clef) {
string t=s;
for (int k=0; k<length(s)-1; ++k) {
string ss=substr(s, k, 1);
for(int j=0; j<alph.length; ++j) {
if (ss==alph[j]) {
t=insert(t, k, clef[j]);
t=erase(t, k+1, 1);
}
}
}
return t;
}

cesar(alph);
string[] T=permutalea(alph);
tableau_de_substitution();
cesar(T,-1);


label("ainsi la phrase :", (-2,-2));
label("devient :", (20,-2));


string[] s={"\footnotesize UN PETIT ROSEAU M'A SUFFI", "\footnotesize POUR FAIRE FREMIR L'HERBE HAUTE", "\footnotesize ET TOUT LE PRE ET LES DOUX SAULES", "\footnotesize ET LE RUISSEAU QUI CHANTE AUSSSI."};
for (int k=0; k<s.length; ++k) {
string t=codemonoalph(s[k], alph, T);
label(s[k], (0,-k-4));
label(t, (20,-k-4));
}


Ca c'est l'ancienne version avec les string[], je suis en train d'adapter tout ça avec string.

GMaths a écrit:Toujours à mélanger les lettres d'un mot ? Si oui, ma solution ne t'allait pas ?


Si, mais je voulais adapter ce que j'avais fait !

Maurice

Re: permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 18:53
par GMaths
maurice a écrit:CA travaille mieux, mais j'aimerais bien comprendre l'erreur précédent

Alors... j'ai regardé ton code... et ton permut_alea est déroutant : pourquoi faire si compliqué pour mélanger ?!??

Mais passons là dessus et parlons de l'erreur... il me semble qu'il y a des k à remplacer par k+1... pour avoir le fonctionnement que tu veux :
Code: Tout sélectionner
if (j != k+1) T2=trans(T2, j, k+1);

Car k=0 pose problème avec trans. s2 était parfois "vide" !

Re: Permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 19:42
par maurice
GMaths a écrit:Alors... j'ai regardé ton code... et ton permut_alea est déroutant : pourquoi faire si compliqué pour mélanger ?!??


C'est un algorithme trouvé sur wikipédia :

Code: Tout sélectionner
Le mélange de Fisher–Yates (en), également appelé mélange de Knuth, est un algorithme en place permettant d'appliquer une permutation aléatoire à n éléments en temps linéaire, les n! permutations possibles étant équiprobables en sortie.

Le principe de cet algorithme est le suivant :

 pour i de 0 à n-1
   j := nombre aléatoire entre 0 et i (inclus)
   si i ≠ j, alors échanger T[i] et T[j]


Il y a sans doute plus efficace ou plu simple (la solution que tu m'as donné) !

GMaths a écrit:Mais passons là dessus et parlons de l'erreur... il me semble qu'il y a des k à remplacer par k+1... pour avoir le fonctionnement que tu veux :
Code: Tout sélectionner
if (j != k+1) T2=trans(T2, j, k+1);

Car k=0 pose problème avec trans. s2 était parfois "vide" !


Merci, je vais regarder tout cela !

Maurice

Edit : ajout du lien

Re: Permutation, transposition, ...

MessagePosté: Vendredi 25 Mars 2011, 19:46
par GMaths
maurice a écrit:C'est un algorithme trouvé sur wikipédia :

ok, ok ! Merci pour le lien.
Heures au format UTC + 1 heure
Page 1 sur 1
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/