[Exercice] Script Anagramme

**jmelyn** · 11/05/2009, 22h17

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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
./anagramme abc
abc
acb
bac
bca
cab
cba

Alors, des idées pour ce petit script?

**noooop** · 12/05/2009, 11h37

Bonjour,

comme je suis assez feignant je préfère laisser la machine trouver toute seule:

parametres: nombre_de_lettres lettre1 ... lettreN

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
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
#!/bin/bash
 
let LENGTH=$1
MAX=$1
COMBINAISONS=1
LETTRES=$2
 
while [ $LENGTH != 1 ]
do
	COMBINAISONS=`expr $COMBINAISONS \* $LENGTH`
	let LENGTH-=1
done
 
echo "Combinaisons: $COMBINAISONS"
 
echo "Nombre de parametres=$#"
 
LETTRES=""
while [  $# != 1 ]
do
	shift
	if [ "$LETTRES" == "" ] ; then
		LETTRES="$1"
	else
		LETTRES="${LETTRES}_$1"
	fi
done
 
echo "Lettres = [$LETTRES]"
 
 
found=0
TOUS_LES_MOTS=""
while [ $found != $COMBINAISONS ] ; do
	let n=0	
	MOT=""
	INDEX_STRING=""
	while [ $n != $MAX ] ; do
		let index_trouve=1
		while [ $index_trouve == 1 ] ; do
			index=`expr $RANDOM % $MAX`
			let trouve=0
			for un_index in $INDEX_STRING
			do
				if [ "$un_index" == "$index" ] ; then
					let trouve=1
				fi
			done
			if [ $trouve != 1 ] ; then
				let index_trouve=0
				INDEX_STRING="$INDEX_STRING $index "
			fi
		done
 
 
		let index+=1
		L=`echo $LETTRES | cut -d _ -f $index`	
		MOT="${MOT}$L"
		let n+=1
	done
 
	let trouve=0
	for un_mot in $TOUS_LES_MOTS
	do
		if [ "$un_mot" == "$MOT" ] ; then
			let trouve=1
		fi
	done
	if [ $trouve == 0 ] ; then
		TOUS_LES_MOTS="${TOUS_LES_MOTS} $MOT"
		let found+=1
		echo "Mot genere ==> [$MOT]"
	fi
done
 
echo "TOUS les mots: [$TOUS_LES_MOTS]"

PS: on ne se moque pas !

PS2: zut j'ai oublié de vérifier que RANDOM ne me retourne pas un entier déjà tiré....je modifirais plus tard

PS3: je penses que ca marche....mais je suis en cours de test
PS4: c'est un peu exponentiel mais ca marche !

**jmelyn** · 12/05/2009, 14h36

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.

**noooop** · 12/05/2009, 15h21

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.

**jmelyn** · 12/05/2009, 20h51

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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
fonction_récursive(argument)
{
  si (argument simple)
  alors
    c'est fini
  sinon
    nouvel_argument = plus_simple(argument)
    fonction_recursive(nouvel_argument)
  finsi
}

On peut maintenant passer au codage...

**jmelyn** · 12/05/2009, 21h14

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.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
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

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.

**jmelyn** · 13/05/2009, 10h35

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
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)
}'

**jmelyn** · 13/05/2009, 10h42

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?

**jmelyn** · 13/05/2009, 10h46

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.

**jmelyn** · 13/05/2009, 14h21

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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
local i
for ((i = 0; i < l_taille_mot; i++))

au lieu de:

 for i in $(seq 0 $(($l_taille_mot - 1)))

Deux remarques:

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...

**noooop** · 13/05/2009, 14h50

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.

[Exercice] Script Anagramme

Shell et commandes GNU

Discussions similaires

Partager

Partager