Il s'agit d'écrire un script qui prend un paramètre et qui écrit toutes les combinaisons possibles des caractères de l'argument:
Alors, des idées pour ce petit script?Code:
2
3
4
5
6
7./anagramme abc abc acb bac bca cab cba
Version imprimable
Il s'agit d'écrire un script qui prend un paramètre et qui écrit toutes les combinaisons possibles des caractères de l'argument:
Alors, des idées pour ce petit script?Code:
2
3
4
5
6
7./anagramme abc abc acb bac bca cab cba
Bonjour,
comme je suis assez feignant je préfère laisser la machine trouver toute seule:
parametres: nombre_de_lettres lettre1 ... lettreN
PS: on ne se moque pas ! :DCode:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
PS2: zut j'ai oublié de vérifier que RANDOM ne me retourne pas un entier déjà tiré....je modifirais plus tard :mouarf:
PS3: je penses que ca marche....mais je suis en cours de test
PS4: c'est un peu exponentiel mais ca marche !
Bravo pour la première réponse! Il s'agit bien d'un exercice, alors des demi-solutions, voire même des quarts, sont les bienvenues. Il y a aussi une petite partie d'algorithmique autour de laquelle on peut discuter: comment faire, quel principe utiliser? Y en a-t-il un meilleur que l'autre. Et puis comment le traduire en Bash (par exemple)? Peut-on utiliser juste une commande évoluée, comme awk? Si vous bloquez, postez quand même: quelqu'un trouvera bien une solution...
Je n'ai pas trop le temps en journée, je verrai ce soir.
Oups, j'ai oublié de documenter la solution.
En fait j'ai appliqué un algo de type "brute force": je cherche aléatoirement toutes les solutions uniques.
Dès que j'ai trouvé un mot unique je le garde dans une variable. Dès que j'ai atteint le MAX de combinaisons unique (factoriel du nombre de lettres) j'arrête.
Bien sur je peux ne jamais trouver de solution....
Pour creer un mot j'utilise RANDOM et je stocke les index retournés par RANDOM pour éliminer les doublons. A chaque index correspond une lettre d'une variable qui ext extraite en utilisant cut.
Je penses que seul AWK est capable de résoudre ce problème.
Bon, par où commencé-je? L'algorithme d'abord: Comment qu'est-ce qu'on fait-on?
(i) Avec deux lettres, a, b, les deux seules anagrammes sont:
a b
b a
(ii) Avec trois lettres, a, b, c:
Je bloque la première lettre: a, puis je fais comme au-dessus avec les deux autres:
a b c
a c b
Ensuite, je bloque la première lettre: b, et idem avec les deux restantes:
b a c
b c a
Enfin, je bloque la première lettre: c, et encore pareil pour les deux autres:
c a b
c b a
(iii) Avec quatre lettres, on bloquera de la même façon la première lettre sur chacune des quatre possibilités, et on utilisera la méthode (ii) pour les trois lettres restantes qui elle-même utilise la méthode (i) pour les deux dernières lettres.
Cette manière de faire s'appelle récursivité: On fait appel à la même procédure, mais en plus simple jusqu'à obtenir la première pierre, comme (iii) utilise (ii) qui utilise (i).
On peut écrire:
On peut maintenant passer au codage...Code:
2
3
4
5
6
7
8
9
10
Pour cette première réponse, je n'utilise que Bash, pas la commande awk. Les noms de variables sont en français; ceux commençant par "l_" sont des variables locales, celui commençant par "t_" est un tableau et celui par "lt_" est un tableau local.
En noir est le programme principal (à la fin), en vert la fonction récursive (qui s'appelle elle-même et qui simplifie un peu à chaque fois), et en bleu les appels de la fonction.Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#!/bin/bash function recurs { local l_taille_mot=${#1} local lt_mot=($(echo $1 | sed 's/\(.\)/\1 /g')) local l_sortie_index=$(($taille_mot - $l_taille_mot)) for i in $(seq 0 $(($l_taille_mot - 1))) do t_sortie[$l_sortie_index]=${lt_mot[i]} nouveau_mot=${1/${lt_mot[i]}/} [[ -n $nouveau_mot ]] && recurs $nouveau_mot done (( $l_sortie_index == $taille_mot - 1 )) && echo ${t_sortie[*]} } declare t_sortie declare taille_mot=${#1} recurs $1
Voici une solution utilisant awk. J'ai repris le plus fidèlement possible le programme Bash: même séquence de commandes, mêmes noms de variables, même couleur de code. On peut ainsi voir facilement les différences entre les deux programmes:
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#!/bin/bash echo $1 | awk ' function recurs(l_mot, l_taille_mot, lt_mot, l_sortie_index, i) { l_taille_mot=split(l_mot, lt_mot, "") l_sortie_index=taille_mot-l_taille_mot+1 for (i=1; i<=l_taille_mot; i++) { t_sortie[l_sortie_index]=lt_mot[i] nouveau_mot=l_mot sub(lt_mot[i], "", nouveau_mot) if (nouveau_mot != "") {recurs(nouveau_mot)} } if (l_sortie_index == taille_mot) { for (j=1; j<=taille_mot; j++) { printf "%c ", t_sortie[j] } print "" } } { taille_mot=length($0) recurs($0) }'
Entre les versions Bash et awk, on voit bien sûr la même structure, mais le code Bash est moins lisible et plus compact (19 lignes contre 27). Par contre, son exécution est 24 fois plus lente (167 ms contre 7).
Il y a beaucoup à écrire sur le codage de chaque version, alors plutôt que de tout expliquer, pourquoi ne pas demander ce qui est peu clair?
Pour la version de noon, je prendrai plus de temps dans quelques jours pour la décortiquer. C'est vraiment original et ça me fait penser à la simulation par la méthode de Monte-Carlo.
Je reviens pour apporter une modification sur le script Bash:
La boucle for est faite grâce à la commande seq. Mais on peut utiliser aussi l'écriture arithmétique:
Deux remarques:Code:
2
3
4
5
6
- i doit être déclaré local, ce qui est normal; inutile dans l'expression utilisant seq. Étrange...
- Question performance, on passe de 167ms à 105 (37% d'accélération!). Re-étrange...
Chapeau !. Je débute en bash si bien que je ne savais pas qu'il y avait des variable locales et des tableaux. Très bon exemple d'application.
J'avais aussi écarté la récursion à cause de celà.
Par contre si je devais donner un point de vue de professionnel, je préfères la version AWK qui me semble plus facile à maintenir.
Sinon pour la petite histoire de mon script, j'avais été voir les algos sur les annagrammes et comme ils étaient très mal écrits (dans le sens lisibilité du code) j'ai eu la flemme de les réécrire en supprimant la récursion.
:D