Discussion :

[jmelyn]

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]

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]

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]

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]

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]

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.