Discussion :

[gwandals]

Bonjour, je cherche a écrire un programme recherchant les anagrammes dans une liste.
Pour cela je voudrais dans un premier temps écrire un fonction permettant de construire la liste des mots du dictionnaire contenus dans un fichier de type txt.

Le type de la fonction, doit être string->list il me semble, et prendra comme argument l'emplacement du fichier.

J'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(*fonction permettant d'accéder au fichier*)
let canal=open_in "C:\Users\Bibiche\Desktop\dico.txt";;
 
(*fonction permettant de lire le contenu de la ligne suivante*)
let ligne_suivante canal=
try input_line canal
with End_of_file -> "EOF" ;;
 
(*Mais je ne vois pas comment construire ma liste à partir de ces fonctions..*)
let construit_dic "C:\Users\Bibiche\Desktop\dico.txt" =
                  .....

[prgasp77]

Bonjour gwandals et bienvenu(e) sur les forums dvp .
Avant toute chose : . Ça permet de rendre le code bien plus lisible (conserve l'indentation et utilise une police à pas fixe).


Quant à ton problème, effectivement le premier pas est de construire une fonction (de type string -> string list) qui lise ton dico.
Il faut en effet utiliser open_in et input_line de la façon dont tu l'as fait.

Pour enregistrer le résultat dans une liste, tu peux procéder de manière itérative :

Code :

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

1
2
3
4
5
6
7
8
<initialiser une string list ref à []>
try
  while true; do
    <ajouter la ligne obtenue via input_line à la string list ref>
  done; []
with End_of_file ->
  close_in chan;
   <inverser l'ordre des éléments de la liste>

Ou de manière récursive (à mon avis bien plus belle)

Code :

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

1
2
3
4
5
6
7
8
let rec loop acc =
   try
      <lire chanel -> lew_line>
      loop (new_line :: acc)
   with End_of_file ->
      <retourner acc inversée>
in
   loop []

[kre75]

Ou de manière récursive (à mon avis bien plus belle)

Code :

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

1
2
3
4
5
6
7
8
let rec loop acc =
   try
      <lire chanel -> lew_line>
      loop (new_line :: acc)
   with End_of_file ->
      <retourner acc inversée>
in
   loop []

Attention, ce code n'est pas récursif terminal !

Code :

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

1
2
3
4
5
6
7
8
9
10
11
$ wget http://www.puzzlers.org/pub/wordlists/unixdict.txt
 
$ > dico.txt
 
$ for i in `seq 5`; do cat unixdict.txt >> dico.txt ; done
 
$ wc -l dico.txt
125520 dico.txt
 
$ ocaml not_tail_rec.ml
Stack overflow during evaluation (looping recursion?)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
$ cat not_tail_rec.ml
let rec loop acc ic =
  try
    let new_line = input_line ic in
    loop (new_line :: acc) ic
  with End_of_file ->
    List.rev acc
 
let () =
  let ic = open_in "dico.txt" in
  let lines = loop [] ic in
  List.iter print_endline lines.

http://rosettacode.org/wiki/Find_lim...ecursion#OCaml

Il faut externaliser le try/with hors de la boucle afin de ne pas casser la récursivité terminale :

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
$ cat tail_rec.ml
let input_line_opt ic =
  try Some (input_line ic)
  with End_of_file -> None
 
let read_lines ic =
  let rec aux acc =
    match input_line_opt ic with
    | Some line -> aux (line::acc)
    | None -> (List.rev acc)
  in
  aux []
 
let () =
  let ic = open_in "dico.txt" in
  let lines = read_lines ic in
  List.iter print_endline lines

Code :

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

1
2
3
4
5
$ ocaml not_tail_rec.ml > /dev/null && echo "OK"
Stack overflow during evaluation (looping recursion?).
 
$ ocaml tail_rec.ml > /dev/null && echo "OK"
OK

http://rosettacode.org/wiki/Read_a_f..._by_line#OCaml

[kre75]

Bonjour, je cherche a écrire un programme recherchant les anagrammes dans une liste.

Attention ne regarde pas ces solutions tout de suite.
Mais à la fin de ton exercice tu pourras trouver des examples d'exercices sur les anagrammes sur Rosetta.

Celui-ci ne les affiche pas tous mais juste les ensembles contenant le plus de mots :

http://rosettacode.org/wiki/Anagrams#OCaml

Celui-ci cherche uniquement les anagrammes dérangés :

http://rosettacode.org/wiki/Anagrams...anagrams#OCaml

A+

[prgasp77]

@kre75 : Te rends-tu compte que tu t'adresse à un débutant OCaml ? De plus, ton intervention ne va pas motiver le PO à résoudre son problème par lui-même, mais plutôt à pomper ce qu'il peut, sans comprendre.
Effectivement on ne va pas ici dès le premier abord chercher la récursion terminale (de toute façon List.rev ne l'est pas) mais à avoir un concept que peut écrire et comprendre un débutant.


@gwandals : Je te conseille d'ignorer les messages de kre75 dans un premier temps. Pour ton information la récursivité terminale est une façon de coder qui permet à OCaml d'optimiser le programme conçu. Si tu es curieux tu pourras en apprendre un peu plus par la suite sur ce sujet. Bon courage !

[kre75]

@kre75 : Te rends-tu compte que tu t'adresse à un débutant OCaml ? De plus, ton intervention ne va pas motiver le PO à résoudre son problème par lui-même, mais plutôt à pomper ce qu'il peut, sans comprendre.
Effectivement on ne va pas ici dès le premier abord chercher la récursion terminale (de toute façon List.rev ne l'est pas) mais à avoir un concept que peut écrire et comprendre un débutant.


@gwandals : Je te conseille d'ignorer les messages de kre75 dans un premier temps. Pour ton information la récursivité terminale est une façon de coder qui permet à OCaml d'optimiser le programme conçu. Si tu es curieux tu pourras en apprendre un peu plus par la suite sur ce sujet. Bon courage !

Tes remarques sont pertinentes, et je les entends bien.
Cependant je souhaiterais apporter un peu de nuances.

Perso j'ai appris la récursivité terminale très tot dans mon apprentissage d'OCaml.
Peut-être dès la première ou deuxième ou troisième semaine.
(Contexte : OCaml n'était pas le Nième langage que j'apprenais, j'étais vraiement débutant)
Et ce pour une raison toute simple : c'est que sans çà on obtient que le message "Stack overflow during evaluation" à tout bout de champ !
Je souhaiterais ainsi me plusoyer moi-même en faisant noter qu'ici on ne connait pas le nombre d'élément du fichier "dico.txt" de notre ami débutant. Si "Stack overflow during evaluation" est tout ce qu'il peut obtenir en le lisant, notre ami débutant ne va pas aller bien loin.

Je me suis également demandé s'il était pertinent de donner des réponses (qui sont proches mais pas identique à ce qu'il cherche à faire) or à la lecture de ses mots "Pour cela je voudrais dans un premier temps écrire [...]" cela montre qu'il a l'esprit nécessaire à l'auto-organisation.

Généralement j'essaie de répondre de la manière où j'aurais aimé être répondu quand j'ai débuté.

Cependant je ne dis pas tout çà pour rejeter tes remarques pertinentes, juste pour les nuancer légèrement.

Bien respectueusement.

[gwandals]

Bonjour, je vous remercie pour vos réponses dans un premier temps.
Je ne doute pas du fait que vous avez essayé de m'apporter la réponse qui vous semblait la plus adapté.
Je n'ai commencé l'informatique que cette année depuis seulement 4 mois (je suis en math spé), et j'ai un peu de mal, pour l'instant cela ne parait pas très intuitif, j'espère que cela va changer.

@kre75: Merci, de ta réponse et tes liens. Il y a certaines expressions dans tes programmes que je ne connais pas, et que je n'ai surement pas encore vu.

@prgasp77: Tes réponses mon données quelques idées, je te remercie.

Je me posais la question, en cours on travail avec le logiciel Caml.light, et non Ocaml, il me semble qu'il y a une différence non ?

[prgasp77]

Si "Stack overflow during evaluation" est tout ce qu'il peut obtenir en le lisant, notre ami débutant ne va pas aller bien loin.

Dans ce cas effectivement il faudra l'aiguiller sur une solution tail rec. Mais je suis à peu près sûr que pour un débutant il est nécessaire de partir d'une solution non tail rec pour parvenir à une qui le soit. Donc un pas après l'autre.

Mais ne t'en fais pas, il ne m'est pas venu à l'esprit de douter de tes intentions d'aider.

Tes réponses mon données quelques idées, je te remercie.

N'hésite pas à poster la première version de ta fonction ; il nous sera alors possible de t'aider à l'améliorer. As-tu aussi une idée de comment − à partir d'une string list − trouver les anagrammes contenus ?

Je me posais la question, en cours on travail avec le logiciel Caml.light, et non Ocaml, il me semble qu'il y a une différence non ?

Oui la différence est notable (ils sont obtus ces profs à opter pour caml light ...). Beaucoup de fonctions de la bibliothèque standard d'OCaml n'existe pas en Caml Light ou ont un autre nom.

Cdlt,

[gwandals]

Envoyé par prgasp77
N'hésite pas à poster la première version de ta fonction ; il nous sera alors possible de t'aider à l'améliorer. As-tu aussi une idée de comment − à partir d'une string list − trouver les anagrammes contenus ?

Oui, j'ai une idée, mais pour cela plusieurs autres fonction me sont nécessaires. En fait je pensais créer:

- une fonction de type string->string pour ordonner les lettres du mot ce qui constituerai en quelque sorte une clé.

-une deuxième fonction qui elle construirait la liste des couples [clé; mot], elle serais de type string list-> (string*string) list.

- et pour finir une dernière fonction de tri à partir des premiers éléments des couples. (composé de trois fonctions, je l'ai écrite.)

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
let rec partage l= match l with 
	|[]        ->([],[])
	|[(a,b)]   -> ([(a,b)],[])
	|h1::h2::r -> let(r1,r2)= partage r in (h1::r1),(h2::r2);;
 
let rec fusion l1 l2 = match l1,l2 with 
	|[],_ -> l2
	|_,[] -> l1
	|(a,b)::c ,(d,e)::f when a = d -> (a,b)::(fusion c l2)
	|(a,b)::c ,(d,e)::f             ->(d,e)::(fusion l1 f);; 
 
let rec trf l = match l with 
	|[]->[]
	|[x]->[x]
	| _ -> let (l1,l2)= partage l in fusion (trf l1) (trf l2);;

Et ensuite donc il me faudra écrire une dernière fonction à l'aide de toute les autres.

[prgasp77]

Je ne comprends pas très bien ton tri fusion : à aucun moment tu ne testes l'ordre des éléments en question, tu ne testes que l'égalité.

Puis-je te suggérer d'utiliser une unique fonction de tri pour la génération des clés comme pour le tri des couples (clé, mot) ? Voici à quoi ressemblerait une telle fonction (c'est pratiquement la même chose que toi, sauf qu'elle prend une liste de « n'importe quoi » − c'est à dire des entiers, des couples, des listes ... n'importe quoi pour lequel tu saurais définir une fonction qui ordonne deux éléments) :

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
let rec merge_sort comp l =
	let rec split l = match l with
	| []		-> ([],[])
	| [h]		-> ([h],[])
	| h1::h2::t	->
		let (l1,l2) = split t in
		h1::l1 , h2::l2
	in
 
	let rec merge l1 l2 = match l1,l2 with
	| _,[]		-> l1 (* si l1,l2 = [],[], on retourne [], soit l1 *)
	| [],_		-> l2
	| h1::t1,h2::t2	->
		if comp h1 h2 > 0
		then h2 :: (merge l1 t2)
		else h1 :: (merge l2 t1)
	in
 
	match l with
	| []	-> []
	| [h]	-> [h]
	| _	->
		let l1 , l2 = split l in
		let merged_l1 = merge_sort comp l1
		and merged_l2 = merge_sort comp l2 in
		merge merged_l1 merged_l2
;;

• split tu la reconnais, c'est ta fonction sauf qu'elle scinde une liste de « n'importe quoi » (en OCaml on donne le nom de 'a − ou 'b, 'c, ... − à un type « joker » : ici 'a list).
• merge est différente de la tienne : elle compare les deux premiers éléments de la liste (h1 et h2). Si h1 > h2 elle place h2 en tête du résultat ; sinon elle place h1 en tête. comp (alias compare) doit être une fonction du type 'a -> 'a -> int ; comp a b retourne 0 si a = b ; retourne 1 si a > b et -1 si a < b. C'est assez courant comme fonction de comparaison.
• merge_sort comp l scinde l en deux, trie récursivement ses deux moitiés et fusionne celles-ci.

Voici un exemple d'utilisation :

Code :

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

merge_sort compare_strings ["bonjour"; "comme";"ça";"va"] ;;

Code :

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

1
2
3
4
5
6
let compare_int a b = (* une fonction toute faite existe déjà en Caml Light ? *)
	if a > b then 1
	else if a < b then -1
	else 0
;;
merge_sort compare_int [5;6;8;0;3;2;3;5;8;0] ;;

Code :

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

1
2
3
4
let compare_keyword_couple a b =
	(* ici ta fonction qui permet de comparer clé1 et clé2 extraites de (clé1,mot1) et (clé2, mot2) *)
;;
merge_sort compare_keyword_couple ["bjnooru","bonjour ; "ehllo","hello"] ;;

... tu peux aussi t'en sortir pour ordonner les lettres d'un mot ("bonjour" → "bjnooru"), il faudra un peu ruser pour cela.


Bon courage.

[gwandals]

Bonjour, merci pour ton aide.
Les fonctions composants ma fonction finale avance peu a peu.
J'ai en partie réussie ma fonction pour ordonner les lettres d'un mot :

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
(*fonction créant le tableau composé des lettres du mot*)
 
let sep_lettre_mot s =
let t=make_vect (string_length s) `a` in 
for i=0 to  (vect_length t)-1 do 
 t.(i) <- s.[i]
done; 
t;;
 
(*fonction triant les lettres de la liste dans l'ordre alphabétique*) 
 
let tri tableau =
for fin=(vect_length tableau)-1 downto 1 do
for i=0 to fin-1 do
if tableau.(i)>tableau.(i+1) then
begin
let temp = tableau.(i) in
tableau.(i)<-tableau.(i+1);
tableau.(i+1)<- temp
end
done 
done;
tableau;;
 
 
(*tri(sep_lettre_mot "chat") ;;   
#- : char vect = [|`a`; `c`; `h`; `t`|]*)

Mais, ma clé est dans un tableau ..

[gwandals]

Je voulais mettre les lettres de mon tableau dans un mot (string) mais ça ne fonctionne pas.. y a t'il une erreur dans ma fonction :

Code :

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

1
2
3
4
5
6
7
let rec calcule_cle t s = (*ou t est mon tableau composé des lettres triées*)
let n = (vect_length t)  in 
for i=0 to n do 
let s= (make_string n `a`) in 
s.[i] <- t.[i]
done; 
s;;

[prgasp77]

Tu n'as pas été cherché bien loin ... Et tu dupliques le code aussi, tu as une fonction de tri pour chaque type de tri que tu fais. C'est dommage.

[gwandals]

J'ai modifié certaines choses. Il est vrai que j'utilise deux fonctions de tri différentes, mais je n'arrive pas a utiliser ma première fonction pour la génération des clés, vu que je suis partie d'un tableau ... J'ai trouvé une fonction prédéfinie pour le second tri, et j'ai gardé mon tri a bulle pour la génération des clés ...

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
 
(*Fonction construit_dic*)
let canal=open_in "C:\Users\Bibiche\Desktop\dico";;
let construit_dic =
let l = ref [] in 
	for i = 1 to 22740 do 
		let s = (input_line canal) in 
		l:=s::(!l);
	done;
!l;;
let dictionnaire = construit_dic;;
 
(*Fonction clacule_cle *)
let calcule_cle s =
let t=make_vect (string_length s) `a` in 
for i=0 to  (vect_length t)-1 do 
 t.(i) <- s.[i]
done; 
for fin=(vect_length t)-1 downto 1 do
for i=0 to fin-1 do
if t.(i)>t.(i+1) then
begin
let temp = t.(i) in
t.(i)<-t.(i+1);
t.(i+1)<- temp
end
done 
done;
let liste= list_of_vect t in
let cle =(make_string (list_length liste) `a`) in
let rec transf liste cle i = match liste with
|[]->cle
|a::[]->begin cle.[i] <- a; cle end
|a::b -> begin cle.[i]<-a; (transf b (cle) (i+1)) end in
transf liste cle 0;;
 
(*Fonction construit_liste_couples*)
 
let construit_liste_couples liste = 
let rec aux liste liste_couples = match liste with
|[] -> liste_couples
|a::b ->aux b ((calcul_cle_mot a,a)::liste_couples) in
aux liste [];;
 
(*Fonction tri_liste_couples, j'utilise ici une fonction prédéfinie sort__sort appliqué à la fonction qui compare les premiers éléments de deux couples et à notre liste*)
 
let tri_liste_couples liste =
sort__sort (fun (a1,a2) (b1,b2) -> a1<=b1) liste;; 
 
 
(Et enfin ma fonction affichant les anagrammes d'un mot du dictionnaire*) 
 
let anagrammes mot = 
let dictionnaire = ref construit_dic in
let liste = ref (tri_liste_couples (construit_liste_couples !dictionnaire)) and clé = ref (calcul_cle_mot mot) in
let rec aux liste clé booleen = match liste with 
|[] -> failwith "Ce mot n'existe pas et ne possède pas d'anagrammes"
|(a,b)::c -> begin if clé = a then begin print_string b; print_newline(); aux c clé true end 
else begin match booleen with
|false -> aux c clé booleen
|true -> () end end
in
aux !liste !clé false;;