Discussion :

[drunkskater]

Salut,

Je préviens que ce que je vais dire risque de ne pas être clair et demande à être confirmé.

Pour les index, il s'agit juste d'une autre façon de parcourir ta chaine de caractère.

En effet, pour l'instant tu as - si je ne me trompe - fait comme si tu travaillais sur une pile / liste, à savoir un truc du genre :

Code :

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

1
2
3
4
let rec parcourir fonction chaine =
  fonction (sub_string chaine 0 1);
  parcourir fonction (sub_string chaine 1 (string_length chaine - 1))
;;

Ici, on applique fonction au premier élément de la chaine de caractère, puis on rappelle parcourir sur le reste de la chaine. Ainsi, la chaine sera bien balayée.

Mais tu remarques qu'on effectue en fait que deux actions sur la chaine : l'accès à son premier élément, et l'accès à la chaine privée de son premier élément. Certaines structures de données (comme les piles ou les listes) sont adaptées à cela. Ainsi, si on devait réécrire exactement le même programme pour une liste on aurait :

Code :

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

1
2
3
4
5
6
let rec parcourir fonction liste =
  match liste with
  | [] -> ()
  | tete :: queue -> fonction tete;
                     parcourir fonction queue
;;

Mais ce n'est pas adaptés pour les chaînes de caractères, car il n'est pas facile d'avoir accès à la chaîne privée de son premier caractère. En effet, les chaînes sont implantées comme des tableaux de caractères, c'est-à-dire un ensemble de n caractères indexés par des entiers de 0 à n-1. Ainsi, quand je vais vouloir avoir accès à une chaîne privée de son premier caractères, il va falloir créer un objet de longueur n-1 puis le remplir avec les bons caractères... Ce qui a une complexité de la longueur de la sous-chaine...

Du coup tu vois l'inefficacité du premier mode de balayage avec les chaînes (et les tableaux) : la complexité va être en (n-1) + (n-2) + ... + 1 = n.(n-1)/2, c'est-à-dire quadratique !

En revanche, la structure "en tableau" offre un autre avantage : il est très simple d'avoir accès au i-ème élément : ça se fait avec la syntaxe chaine.[i], et c'est "immédiat" (contrairement aux listes et aux piles, où il va falloir parcourir l'objet en ayant un compteur pour s'arrêter au i-ème élément). Du coup, il faut s'en servir !

Ainsi, la première fonction devient tout simplement :

Code :

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

1
2
3
4
5
6
(* l'index est ici i *)
 
let rec parcourir fonction chaine =
  let n = string_length chaine in
  for i = 0 to n - 1 do fonction chaine.[i] done
;;

soit, sans boucle for (mais là c'est très moche) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(* l'index est ici n *)
 
let parcourir fonction chaine =
  let auxiliaire n = 
    match n with
    | -1 -> ()
    | n -> fonction chaine.[n];
             auxiliaire (n - 1)
  in
  auxiliaire ((string_length chaine) - 1)
;;

Attention, il y a une petite inexactitude dans ce que j'ai dit (mais j'étais obligé pour ne pas dévoiler la notation chaine.[i] trop tôt) :

sub_string renvoie une chaine de caractère (string), alors que chaine.[i] renvoie un caractère (char). Donc dans la première version fonction est de string -> 'a, alors que dans la dernière version elle est de char -> 'a
(en gros c'est la différence entre "a" et `a`, ou même entre [|`a`|] et `a`...)

J'espère avoir été clair !

[Freedom57]

Si tu as le droit d'utiliser List.sort

Et ben non , pas le droit.
@drunkskater
je crois avoir compris l'essentiel de ton post mais je n'ai pas le droit au tableau non plus.
Merci quand même , ça me servira quand enfin je pourrais m'en servir...
Donc en attendant je pense que je n'ais pas le choix d'écrire un code qui sera quadratique...

[gasche]

Son code n'utilise pas de tableaux, mais uniquement des chaînes de caractère. Si tu as peur d'écrire (foo.[n]), tu n'as qu'à écrire (nth_char foo n), c'est exactement la même chose.

Puisque tu utilises déjà "nth_char foo 0", pourquoi ne pas utiliser foo.[n] ?

Je pense que tu as mal compris les restrictions qu' "on" t'impose et que tu fais du code inutilement compliqué. Le code vient en priorité, les consignes délirantes sont à prendre avec recul.

[drunkskater]

Je te conseille de suivre les conseils de bluestorm.

Tu peux écrire :

Code :

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

1
2
3
4
5
6
7
8
9
let parcourir fonction chaine =
  let rec auxiliaire n = 
    match n with
    | -1 -> ()
    | n -> fonction (nth_char chaine n);
             auxiliaire (n - 1)
  in
  auxiliaire (string_length chaine - 1)
;;

mais, étant donné que c'est rigoureusement équivalent à :

Code :

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

1
2
3
let parcourir fonction chaine =
  for i = 0 to (string_length chaine - 1) do fonction chaine.[i] done
;;

Est-ce que c'est pas juste bêtement plus moche et moins clair ?

Il faut adapter ta programmation aux objets avec lesquels tu travailles. Ou alors, si tu ne veux pas travailler avec tel type d'objet mais avec un autre, tu peux commencer par convertir les objets (à condition que ça n'affecte pas la complexité). Par exemple, si tu veux absolument travailler avec des structures type piles / listes, tu peux commencer par convertir ta chaine de caractères ( = ton tableau de caractères ) en liste de caractères. Exemple :

Code :

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

1
2
3
4
5
6
7
8
let convertir chaine =
  let rec auxiliaire index accu =
    match index with
    | -1 -> accu
    | n -> auxiliaire (index - 1) ((nth_char chaine n) :: accu)
  in
  auxiliaire (string_length chaine - 1) []
;;

(Tu remarques que je n'ai pas utilisé de boucle for ni la notation chaine.[n] )

Ensuite, tu travailles comme tu veux avec ta liste de caractères. Sauf qu'au lieu d'utiliser sub_string chaine 1 (string_length chaine - 1) tu pourra utiliser tl (ou, mieux car plus lisible, faire un match sur ta liste comme je l'ai fait dans mon message précédent)

Ceci dit, je répète que cette solution n'est pas (du moins dans le cas présent) intéressante. Mais ça sera toujours mieux que de travailler avec une pile qui n'en est pas une avec sub_string et de se retrouver avec une complexité quadratique !

PS :

Je me suis rendu compte qu'il y avait quelques erreurs de syntaxe dans mon message précédent, j'espère que tu t'en étais rendu compte parce qu'il y avait aucune chance pour qu'elles marchent. Je les ai corrigées, mais je ne garantis pas qu'elles marchent !

PPS : C'est bizarre, il est impossible d'indenter un code correctement, même avec la balise "code" (ça fait des trucs bizarres avec mes espaces...). Plutôt surprenant pour un forum de programmation, à moins qu'il y ait une subtilité que je n'ai pas comprise ?

[UnboundID]

Si tu as le droit d'utiliser List.sort, je pense que mon algo est le plus simple à mettre en place (tu dois réécrire quelques lignes pour enlever les traits impératifs, mais c'est simple).

Freedom57, comme tu utilises Caml Light, une réécriture de l'algo de LLB pourrait être :

Code :

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

1
2
3
4
5
6
7
8
let to_sorted_list s =
  let l = string_length s
  in let rec aux i = 
       if i = l then []
       else (nth_char s i)::aux (i+1)
     in sort (fun x y -> x < y) (aux 0);;
 
let anagramme x y = to_sorted_list x = to_sorted_list y;;

Bien sûr pour utiliser sort, il faut charger le module éponyme

Code :

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

#open "sort";;

ou bien l'écrire soi-même, ce qui est un bon entrainement quand on débute.

Pour répondre à ta question initiale, dans le corps de ta fonction anagramme je compte 7 let pour seulement 6 in. Le in manquant correspond vraisemblablement au let de parcourir. Une indentation qui aligne le let au in correspondant permet de voir facilement ce genre d'omission.

PS : la solution de drunkskater dans le post précédent te permettra de mieux coller à ce que tu souhaitais faire initialement.

[drunkskater]

Je ne pense pas qu'il ait le droit d'utiliser sort, même en Camllight : Par exemple l'année dernière on m'interdisait l'utilisation de toute fonction "non élémentaire" comme map ou iter (et même parfois sub_string), justement pour nous forcer soit à les réécrire soit à trouver d'autres algorithmes et à ne pas sombrer dans la facilité (ce qui est un peu le cas avec le coup du tri "tout fait" de la liste)

Quant à réécrire soit même une fonction de tri, c'est évidemment une bonne idée pour l'entraînement, mais ça me semble plus compliqué que le problème de départ

[UnboundID]

Par exemple l'année dernière on m'interdisait l'utilisation de toute fonction "non élémentaire" comme map ou iter (et même parfois sub_string), justement pour nous forcer soit à les réécrire soit à trouver d'autres algorithmes et à ne pas sombrer dans la facilité (ce qui est un peu le cas avec le coup du tri "tout fait" de la liste)

Je suis sûr qu'il doit avoir écrit, ou qu'il faudra bientôt qu'il écrive, au moins une fonction de tri en TD ou en TP.

[drunkskater]

Je suis sûr qu'il doit avoir écrit, ou qu'il faudra bientôt qu'il écrive, au moins une fonction de tri en TD ou en TP.

Oui ça c'est sûr ! Mais - outre le fait que ces algorithme me semblent (mais c'est subjectif) plutôt plus compliqués que la fonction anagramme - ça sera probablement un truc en O(n²), au mieux en O(n.log(n)), et donc ça me semble dommage d'y avoir recours alors que fondamentalement il y a plus simple et plus efficace pour savoir si deux chaines de caractères sont des anagrammes.

[Freedom57]

Bon voilà un code qui tourne , je ne déclare pas les fonctions en locales afin que le code soit plus clair sur le forum.

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
 
let rec creer_liste ch l n=(*change une chaine en liste*)
if n>(-1) then match l with
			[]->creer_liste ch (ch.[n]::[]) (n-1)
			|x::r->creer_liste ch (ch.[n]::l) (n-1)
		else l;;
 
let rec supprime c l=
match l with
[]->failwith "erreur"
|x::[]->if x=c then [] else l
|x::r->if x=c then r else x::(supprime c r);;
 
let rec appartient l1 l2=
	match (l1,l2) with
	([],[])->`v`
	|(x::[],y::[])->if (x=y) then y else `1`
	|(x::r,y::[])->if (x=y) then y else  `1`
	|(x::r,y::t)->if (x=y) then y else (appartient l1 t);;
 
let rec parcours l1 l2=
	let c=(appartient l1 l2) in
	match c with
        `1`->false
	|`v`->true
	|x->parcours (supprime x l1) (supprime x l2);;
 
let annagramme ch1 ch2=
	let long1=string_length ch1
		and long2=string_length ch2
	in if long1=long2
		then let l1=creer_liste ch1 [] (long1-1)
				and l2=creer_liste ch2 [] (long2-1)
			in parcours l1 l2
		else false;;

C'est betement plus moche et moins clair sans les boucles , mais je n'ai pas le droit aux boucles...

Par contre j'ai bien utiliser foo.[n] qui est clairement interressant.

Je me doute bien que ce code doit pouvoir être optimisé.Donc je suis preneur de vos suggestions...

Et oui , pour le tri , on a vu vite fait "quick sort" en cours.Et il faudrait effectivement que j'essaie de le recoder.

En attendant , merci pour votre aide.

Cordialement,

Freedom.

[Cacophrene]

Bonjour,

Je me doute bien que ce code doit pouvoir être optimisé

Tu peux effectivement simplifier ton code en identifiant clairement les étapes-clefs de ta stratégie. Par exemple, voici une stratégie qui ressemble beaucoup à la tienne :

• Transformer les mots A et B en listes de caractères T1 et T2.
• Retirer chaque lettre rencontrée dans T1 de la liste T2.
• Lorsque T1 a été entièrement parcouru, T2 doit être vide.

Nous avons donc besoin de trois fonctions (écrites volontairement sans itérateurs) :

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
let explode str =
  let rec loop acc = function
    | 0 -> acc
    | i -> let j = i - 1 in
      loop (str.[j] :: acc) j
  in loop [] (String.length str)
  
let rec remove chr = function
  | [] -> []
  | x :: y when Char.compare x chr = 0 -> y
  | x :: y -> x :: remove chr y
  
let anagram word1 word2 =
  let rec loop t2 = function
    | [] -> t2 = []
    | chr :: y -> loop (remove chr t2) y
  in loop (explode word2) (explode word1)

La fonction explode n'est utilisée qu'au lancement pour convertir les chaînes de caractères en listes de caractères. Elle procède de la fin de la chaîne vers le début afin d'insérer les éléments dans la liste avec l'opérateur cons (::). La fonction remove supprime un caractère donné dans une liste reçue en entrée. C'est elle qui permet d'enlever un à un les caractères du second mot à mesure qu'ils sont rencontrés dans le premier mot. Enfin, la fonction anagram parcourt le premier mot et effectue les appels à remove pour biffer les caractères les uns après les autres. Deux mots sont des anagrammes si, à la fin du parcours, la liste du second mot (t2 dans mon code) est vide.

J'attire ton attention sur le fait que ce code est moins efficace que les petits codes plus ou moins "polémiques" que nous t'avons donné auparavant. As-tu une idée de ce qui se passe dans le pire des cas, avec cette approche ?

Cordialement,
Cacophrène

[gasche]

Le code est correct (je n'ai pas regardé en détail) mais l'algorithme reste quadratique en la taille des mots. Le coût quadratique vient du fait que tes fonctions "appartient" et "supprime" ont un coût linéaire.
Tu ne pourras pas faire mieux sans une structure de donnée qui permet l'accès arbitraire en temps constant, ie. un tableau (on pourrait tricher avec une chaîne, mais ce serait tricher), ou une structure plus complexe permettant l'accès logarithmique (comme 'map' et 'set' de la bibliothèque standard, mais bien sûr tu n'as pas le droit non plus de les utiliser).

Je pense donc que tu peux t'estimer satisfait de cette version : c'est naïf mais honnête, et sans tableau tu ne feras pas significativement mieux.

Un conseil : même si tu n'as pas le droit d'utiliser la bibliothèque standard, je te conseille de t'y familiariser. Pour deux raisons :

- Je ne sais pas quel cursus délirant tu suis, mais dans les endroits sensés ont encourage au contraire les étudiants à réutiliser la bibliothèque standard (dans la mesure du raisonnable : on n'utilise pas sort__sort dans un exercice dont le but est d'implémenter un tri) et ton code serait donc considéré comme inutilement redondant (recoder ce qui existe c'est multiplier les chances de bug sans rien apporter). Pour éviter d'être complètement démuni si tu te retrouves dans ce contexte, il est bon de connaître les principales fonctions de la bibliothèque pour pouvoir changer facilement ton fusil d'épaule.

- La bibliothèque standard est orientée autour de blocs abstraits qui sont utiles dans de nombreuses situations. Tu as eu le flair nécessaire pour découper les opérations "appartient" et "supprime" (`mem` et `except` en Caml Light), mais il y a des opérations utiles qu'il n'est pas forcément naturel d'inventer soi-même, je pense par exemple à `map` et `iter` : les débutants ont tendance à ré-écrire plusieurs fois des spécialisations de ces fonctions à un cas particulier. Connaître les fonctions générales permet de te donner des idées sur comment mieux structurer les fonctions de ton application (par exemple recoder map au lieu de recoder un cas particulier de map).


Edit : je n'avais pas vu la remarque de Cacophrène et ses commentaires sont bien sûr pertinents. Je crains d'avoir vendu la mèche sur la complexité, mais c'est la vie.

[Cacophrene]

Re,

Je crains d'avoir vendu la mèche sur la complexité, mais c'est la vie.

La vie est dure

Cordialement,
Cacophrène

[TropMDR]

Code :

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

1
2
3
...
  | x :: y when Char.compare x chr = 0 -> y

Pourquoi pas un simple "when x = chr" ? Pour éviter que la fonction soit polymorphe ? (une annotation de type règle le problème dans ce cas) Pour l'efficacité ? (une annotation de type règle le problème dans ce cas aussi )


Mais sinon rien à redire

[Cacophrene]

Re,

Pourquoi pas un simple "when x = chr" ? Pour éviter que la fonction soit polymorphe ? (une annotation de type règle le problème dans ce cas) Pour l'efficacité ? (une annotation de type règle le problème dans ce cas aussi )

De deux choses l'une : d'une part, il est idiomatique d'éviter les annotations de type en OCaml; d'autre part les optimisations de cette nature sont inutiles tant qu'un code est algorithmiquement mauvais (c'est-à-dire quadratique alors que des solutions quasi-linéaires et linéaires ont été proposées dans le fil). Peut-être qu'il n'y a pas toujours de raison précise... tout simplement.

Cordialement,
Cacophrène