Discussion :

[Remmal]

Bonsoir à tous,

J'ai quelques difficultés pour transformer un vecteur.
En effet j'ai écrit un programme pour décomposer une permutation en produit de cycles, qui est le suivant :

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
 
let id x = init_vect x (fun t -> t);;
 
let max v = 
let r,n = ref v.(0), vect_length v in 
     for i=0 to (n - 1) do
         if !r < v.(i) then 
		 r := v.(i) 
     done;
!r
;;
 
let predecomp v = 
let n = vect_length v in
     let (v',v'',r,j)= ((copy_vect v) , (id n) , (ref (max v)) , (ref (max v))) in
         begin 
	     v'.(0) <- !r;
             v''.(!r) <- 0;
             r := v.(!r) 
	     end; 
     for k = 1 to n - 1 do
         if v.(v'.(k-1)) <> !j  then
             begin 
		 v'.(k) <- !r;
                 v''.(!r) <- 0;
                 r:=v.(!r) 
		     end
         else 
		     begin
      	         v'.(k) <- max v'';
                 r := v.(max v'');
                 j := max v'';
                 v''.(max v'') <- 0 
			 end
     done;
v'
;;

Ainsi, on obtient

Code :

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

1
2
3
#predecomp [|6;10;13;9;14;1;3;0;11;7;5;2;12;8;4|];;
- : int vect = [|14; 4; 13; 8; 11; 2; 12; 10; 5; 1; 9; 7; 0; 6; 3|]

Ce qui est juste, mais j'aimerais que le résultat s'affiche d'une manière différente. C'est à dire :

[|9; 7; 0; 6; 3; 10; 5; 1; 12; 13; 8; 11; 2; 14; 4|].

En effet les cycles dans ce cas sont (14,4) (13,8,11,2) (12) (10,5,1) (9,7,0,6,3).

Et au lieu de les afficher dans l'ordre décroissant des éléments de tête j'aimerai le faire dans l'ordre croissant de ces même éléments de tête. Ce que je n'arrive pas à faire...

Merci d'avance,

Remmal.

[Cacophrene]

Bonsoir,

Boucles + références + tableaux : à mon avis tu devrais pouvoir trouver une solution plus dans l'esprit de caml. Bon ça ne répond pas à la question... mais peut-être que tu trouveras comment faire avec cette autre façon d'écrire la solution.

Cordialement,
Cacophrène

[Remmal]

Re-bonsoir,

J'ai chercher un certain bout de temps une autre solution, mais j'aurai besoin de précisions sur une chose. Qu'est ce que tu appelle précisément " l'esprit Caml ", la question peut paraître stupide (d'ailleurs elle l'est peut-être) mais il me semble que c'est quand même l'une des choses les plus importantes à comprendre.
Surtout si je ne suis pas du tout dans cet esprit... Cela signifierait que je perd tout l'intérêt d'utiliser ce langage de programmation.

Remmal.

[InOCamlWeTrust]

L'esprit dans lequel tu abordes la question est le bon, étant donné que tu as affaire avec des traitements très itératifs et que tu utilises des vecteurs. Cacophrène parle essentiellement d'un style plus fonctionnel, avec des appels récursifs dans tous les sens et l'utilisation de listes. Mais ici, ce n'est pas le cas. Je déconseille, d'ailleurs, d'utiliser un style fonctionnel avec des vecteurs, car c'est source d'erreurs. Lorsque tu manipules des vecteurs et que tu les modifies, l'environnement, c'est-à-dire les valeurs visibles depuis un certain point dans le code, ne conserve aucune trace explicite de ces modifications. Ceci couplé à l'utilisation de la récursivité peut rendre des codes très difficiles à débuger... et obscurs à la lecture.

En ce qui concerne ton problème, une solution bête, naïve, consiste à créer un deuxième vecteur, parcourir le premier et copier les cycles. Lorsque tu rencontres un cycle commençant par un nombre supérieur à celui du premier cycle de la copie, tu déplaces tous les éléments du nouveau vecteur vers la droite du nombre de cases nécessaires. Sinon, tu parcours la copie et tu ne déplaces, toujours vers la droite, que les éléments des cycles commençant par un nombre inférieur. Ton vecteur de copie doit en permanence rester trié en sens décroissant. C'est ton invariant de boucle.

[Cacophrene]

Bonjour,

Il y a au moins matière à se passer de références, sans pour autant utiliser les listes. Ça revient toujours à écrire une boucle, mais de façon moins ouvertement « impérative » (le mot est mal choisi).

Cordialement,
Cacophrène

[gasche]

Le problème de fond de ta fonction c'est que le résultat n'est pas sémantique : tu donnes l'ordre dans lequel apparaissent les cycles, mais le tableau que tu renvoies ne permet pas de comprendre les limites des différents cycles.

Pour manipuler facilement ces résultats, il faut que tu utilises une structure de donnée adaptée, qui permette de représenter le sens de ta fonction. Ici, il faut impérativement que tu stockes chaque cycle séparément pour pouvoir les distinguer (donc un tableau de tableaux, une liste de listes, ou une variation dans ce style).

J'ai fait cette modification, et elle renvoie une liste de cycles, ce qui devrait te permettre de résoudre ensuite facilement ton problème (avec un tri, des décalages circulaires, ou n'importe quoi qui te fait plaisir). Le reste de ce message décrit la méthode que j'ai employée : je suis parti de ton code, que je trouve absolument incompréhensible, et je l'ai modifié par étapes pour obtenir un programme (toujours partiellement incompréhensible) qui fasse ce que je voulais.

Au départ, je ne comprenais pas du tout ton code. Je ne connais pas l'algorithme utilisé (mais j'ai une idée de comment résoudre le problème), et je ne comprenais rien aux variables que tu utilisais (v' ? v'' ? r ? j ?). J'ai commencé par renommer légèrement tes deux fonctions auxiliaires :
- "id" désigne traditionnellement la fonction "identité", ton choix est donc ici maladroit, je l'ai appelée "seq" (séquence, sous-entendu d'entiers consécutifs); on doit pouvoir trouver un meilleur nom
- "max" est une fonction déjà existante dans caml, qui renvoie le maximum de deux éléments, j'ai donc appelé la tienne "vect_max"

Code :

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

1
2
3
4
5
6
7
8
9
let seq x = init_vect x (fun t -> t);;
 
let vect_max v = 
  let r = ref v.(0) in 
  for i=0 to vect_length v - 1 do
    r := max !r v.(i)
  done;
  !r
;;

Ensuite je me suis attaqué à la fonction méchante. Le principal problème est de comprendre la signification de v'. Tu la définis comme une copie de v, ce qu'on fait en général quand on veut éviter de modifier le tableau initial. En fait :
- tu n'écris jamais dans v
- tu ne lis jamais dans v', donc le fait qu'il contienne au départ une copie de v n'a pas d'intérêt (à part pour embrouiller le lecteur)
- tu renvoies v' à la fin, donc je l'ai appelé "res" (résultat), initialisé à 0 partout

Comme v'' et v n'ont rien à voir (en général on utilise le prime quand il y a un lien entre les variables), je l'ai renommé en w.

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
let predecomp v = 
  let n = vect_length v in
  let result = make_vect n 0 in
  let w = seq n in
  let j = ref (vect_max v) in
  let r = ref v.(!j) in
  result.(0) <- !j;
  w.(!j) <- 0;
  for k = 1 to n - 1 do
    if v.(result.(k-1)) <> !j  then
      begin 
	result.(k) <- !r;
        w.(!r) <- 0;
        r := v.(!r) 
      end
    else 
      begin
        j := vect_max w;
      	result.(k) <- !j;
        r := v.(!j);
        w.(!j) <- 0 
      end
  done;
  result
;;

Une fois qu'on en est là, on peut réfléchir sur la modification à faire. Ce qu'on voudrait c'est stocker chaque cycle séparément. On veut donc savoir quand commence un nouveau cycle, et/ou quand termine l'ancien cycle. Mon idée est de stocker chaque cycle dans une liste, et de renvoyer à la fin une liste des résultats. J'introduis donc deux variables à la place de ton tableau "result" :
- "cycle", une référence sur une liste, qui contient le cycle (partiel) courant
- "result", une référence sur une liste (de listes), qui contient les cycles terminés déjà trouvés
- une fonction "push" qui ajoute à une liste référencée un élément

Il suffit donc d'ajouter les éléments dans la liste "cycle" tant qu'on est dans un cycle. Quand on constate que le cycle est terminé, et qu'on passe à un nouveau cycle, on exécute les étapes suivantes :
- on met l'ancien cycle dans la liste "result" (on pense à retourner la liste (fonction 'rev'), pour éviter d'avoir les éléments ajoutés en dernier en première position)
- on réinitialise la variable "cycle" pour commencer un nouveau cycle

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
let predecomp v = 
  let n = vect_length v in
  let push li x = li := x :: !li in
  let result = ref [] in
  let cycle = ref [] in
  let w = seq n in
  let j = ref (vect_max v) in
  let r = ref v.(!j) in
  cycle := [!j];
  r := v.(!j);
  w.(!j) <- 0;
  for k = 1 to n - 1 do
    if v.(hd !cycle) <> !j  then
      begin
        push cycle !r;
        w.(!r) <- 0;
        r:=v.(!r)
      end
    else 
      begin
        push result (rev !cycle);
        j := vect_max w;
        cycle := [!j];
        r := v.(!j);
        w.(!j) <- 0 
      end
  done;
  push result (rev !cycle);
  !result
;;

Test :

Code :

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

1
2
#predecomp [|6;10;13;9;14;1;3;0;11;7;5;2;12;8;4|];;
- : int list list = [[9; 7; 0; 6; 3]; [10; 5; 1]; [12]; [13; 8; 11; 2]; [14; 4]]

Edit : il y a une légère subtilité : dans ton algorithme, il n'est pas tout à fait vrai que tu ne lis jamais dans v'. Tu lis la case v'.(k-1) en début de boucle, mais seulement après y avoir écrit : c'est pour accéder au dernier élément considéré. Pour faire cela, je demande le dernier élément ajouté dans le cycle courant : (hd cycle). C'est valide car la liste "cycle" n'est jamais vide : même quand on change de cycle on met immédiatement un élément dedans.

[Cacophrene]

Bonjour,

je crois que bluestorm a très bien détaillé l'impression générale de confusion qui a motivé mon premier message.

Cordialement,
Cacophrène

[gasche]

La même fonction, en récursif :

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 next_not_found found =
  let res = ref None in
  for i = 0 to vect_length found - 1 do
    if not found.(i) then res := Some i
  done;
  !res
;;
 
let predecomp' v =
  let n = vect_length v in
  let found = make_vect n false in (* éléments déjà pris en compte *)
  let rec decomp result cycle = match cycle with
    | i::_ ->
        let j = v.(i) in (* élément suivant *)
        if found.(j) (* si j déjà trouvé, le cycle est fini *)
        then decomp (rev cycle :: result) []
        else begin
          found.(j) <- true;
          decomp result (j :: cycle)
        end
    | [] -> match next_not_found found with
        | None -> result
        | Some i ->
            found.(i) <- true;
            decomp result [i] in
  decomp [] []
;;

Au lieu de ton tableau v''/w, j'ai utilisé un tableau de booléens, "found", qui indique seulement si l'élément a déjà été pris en compte. C'est plus élégant que ton "w.(...) <- 0" puisque on comprend bien la signification de l'opération : on ne s'intéresse pas à la valeur 0, mais au fait qu'on ait déjà trouvé l'élément ou pas. Du coup, j'utilise la fonction "next" à la place de ton "max".

Une optimisation supplémentaire est de s'arrêter dès qu'on trouve le premier élément intéressant. On peut le faire avec une récursion, une boucle "while" ou une exception :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let next_not_found found =
  let res = ref None in
  try
    for i = 0 to vect_length found - 1 do
      if not found.(i) then begin
        res := Some i;
        raise Exit
      end
    done; raise Exit
  with Exit -> !res
;;

[Remmal]

Bonsoir,

Merci beaucoup bluestorm pour toutes les précisions que tu m'as apporté.
Je note bien toutes les remarques faites (notamment sur les "noms" des variables et la lisibilité du code), en tout cas je pense avoir saisi tout ce que tu a fait !

Encore mille Merci !

Remmal

[Onimaru]

Salut,
D'après votre article vous avez écrit un algorithme de décomposition des permutations en transposition(permutation de 2 éléments), pouvez-vous écrire son algorithme en C de façon à afficher les transpositions qui ont été faites. Les entrées sont les vecteurs(tableaux) V1 et V2.
Par exemple :
V1 : (1,5,10,2)
V2 : (5,1,2,10)

résultat :
transposer V1[0] avec V1[1]
transposer V1[2] avec V1[3]

l'algorithme est supposé afficher le minimum de permutations nécessaires pour transformer V1 en V2, donc le nombre de ces transpositions est au maximum n-1 avec n la dimension(taille du tableau) du vecteur V1 (ou V2).

Merci d'avance.

[ManusDei]

Le code du premier message est écrit de manière très largement impérative.

Tu devrais pouvoir t'en inspirer pour retrouver l'algorithme impératif assez facilement.

[SpiceGuid]

Il ne faut pas traduire le code il faut comprendre l'algorithme.
Il s'agit probablement du même algo que sur le site de Zavonen :

http://gilles.dubois10.free.fr/Bases...ns/cycles.html