Discussion :

[Remmal]

Bonjour,

Étant un tout jeune débutant en Caml, j'ai quelques difficultés à programmer une fonction qui reverrait un vecteur d'entiers compris entre 0 et (n-1) où chacun n'apparaitrait qu'une fois et une seule.

Pour l'instant j'ai programmer la boucle suivante qui ne fonctionne pas, car évidemment le fait que l'on puisse tomber deux fois sur le même entier avec random__int crée des problèmes.

Code :

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

1
2
3
4
5
6
7
8
9
 
let randbij n = 
  let v = make_vect n (-1) and r,x = ref 0,ref(random__int n) in
    for k=0 to (n-1) do
       if v.(!x)=(-1) then v.(!x)<- !r
       else r := !r-1;
    r:= !r+1; x:= (random__int n) 
    done;
v ;;

Existerait t il une fonction Caml permettant de générer un entier dans un intervalle de manière unique ? Sinon auriez vous quelques indications à me donner pour que je puisse remédier à mon problème.

Merci,

Remmal.

[Cacophrene]

Bonjour !

Voici une autre manière de procéder :

• Créer le tableau d'entiers ordonné, par exemple [|0; 1; 2; 3; 4|]
• Tirer au sort des couples d'entiers i et j compris entre 0 et n - 1
• Les utiliser pour permuter vect.(i) et vect.(j)

De cette façon tu obtiens un tableau contenant une et une seule fois les entiers entre 0 et n - 1, rangés dans un ordre aléatoire. Je te donne un code en OCaml (je ne pratique pas caml-light) dont tu peux t'inspirer :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(* Permute les deux éléments d'indice i et j du tableau reçu en entrée. *)
let swap t i j =
  let tmp = t.(j) in
  t.(j) <- t.(i);
  t.(i) <- tmp

let shuffle n =
  Random.self_init ();
  let t = Array.init n (fun i -> i) in
  for x = 1 to n do
    swap t (Random.int n) (Random.int n)
  done;
  t

Cordialement,
Cacophrène

[Remmal]

En effet, c'est une excellent idée.
Je met la solution ci-dessous si elle peut servir à quelqu'un

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
let vswitch i j v = 
  let t = v.(i) in
v.(i) <- v.(j);
v.(j) <- t;;
 
let randbij n = 
let v = id n in 
   for k=0 to (n-1) do
   vswitch (random__int n) (random__int n) v done;
v;;

Merci beaucoup Cacophrène,

Remmal.

[gasche]

Cette méthode est mauvaise : les permutations générées ne sont pas uniforméments réparties.

Voici la règle à suivre quand on veut faire des modifications aléatoires uniformes : ne jamais utiliser de méthode dont on ne sache pas prouver (au moins informellement) qu'elles sont correctes.

Je ne sais pas exactement pourquoi la méthode de Cacophrène ne donne pas des résultats uniformes, mais j'observe empiriquement que ce n'est pas le cas. J'utilise pour cela une fonction qui fait beaucoup d'essais et compte le nombre de tableaux générés :

Code :

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

1
2
3
4
5
6
7
8
9
10
let mesure genere nb_iterations =
  let table = Hashtbl.create 100 in
  for i = 1 to nb_iterations do
    let valeur = genere () in
    Hashtbl.replace table valeur
      (1 + try Hashtbl.find table valeur with Not_found -> 0)
  done;
  List.sort (fun a b -> compare (fst a) (fst b))
    (let accu v occ li = (occ, v) :: li in
     Hashtbl.fold accu table [])

Les résultats renvoyés par le code proposé par Cacophrène sont non-uniformes :

Code :

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

1
2
3
4
# mesure (fun () -> shuffle 3) 100000;;
- : (int * int array) list =
[(14819, [|1; 2; 0|]); (14944, [|2; 0; 1|]); (17120, [|2; 1; 0|]);
 (17260, [|1; 0; 2|]); (17264, [|0; 2; 1|]); (18593, [|0; 1; 2|])]

(J'ai évidemment testé plusieurs fois, et c'est toujours la même déviation qui est observée pour les mêmes permutations, ce n'est pas un artefact statistique)

Voici un bon algorithme pour mélanger aléatoirement un tableau :

Code :

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

1
2
3
4
5
let shuffle_tab t =
    let n = Array.length t in
    for i = n - 1 downto 1 do
      swap t i (Random.int (i+1))
    done

On peut facilement se convaincre et vérifier que la permutation est bien uniforme : le choix du dernier élément est uniforme (Random.int n), donc celui de l'avant-dernier aussi, etc.

Voici le code pour obtenir la même interface que le code de Cacophrène :

Code :

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

1
2
3
4
let blue_shuffle n =
  let t = Array.init n (fun i -> i) in
  shuffle_tab t;
  t

Tests :

Code :

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

1
2
3
4
# mesure (fun () -> blue_shuffle 3) 100000;;
- : (int * int array) list =
[(16430, [|1; 0; 2|]); (16468, [|1; 2; 0|]); (16555, [|2; 1; 0|]);
 (16735, [|2; 0; 1|]); (16797, [|0; 1; 2|]); (17015, [|0; 2; 1|])]

Cette fois, les résultats sont dans la marge statistique, et ce ne sont pas toujours les même permutations qui reviennent le plus souvent. De plus, l'algorithme est sensiblement plus rapide (deux fois moins d'appels aléatoires).



(Si vous n'avez pas confiance en cette approche empirique, vous pouvez aussi énumérer toutes les permutations possibles avec la méthode de Cacophrène, et constater qu'elles n'ont pas toutes la même probabilité; mais c'est un peu plus de travail)

[SpiceGuid]

Ok, mais combien faut-il faire d'échanges aléatoires pour réaliser une permutation ?
n ?
2n ?
n² ?

En attendant une réponse avisée (mon petit doigt me dit que la réponse est 2n) je préfère réaliser une vraie permutation, comme ça je suis certain que c'est bien mélangé.

Code :

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

1
2
3
4
5
6
7
8
 
let shuffle n =
  Random.self_init ();
  let t = Array.init n (fun i -> i) in
  for i = 0 to n - 1 do
    swap t i (i + Random.int (n - i))
  done;
  t

edit: grillé par bluestorm

[Cacophrene]

Bonsoir,

Mon code a probablement deux problèmes : d'abord il y a Random.self_init qui est appelé dans shuffle à chaque fois, je ne crois pas que ce soit une bonne idée, et de plus le choix de n permutations est arbitraire (cf post de SpiceGuid ci-dessus).

Redescendons sur terre : est-ce que le PO a vraiment besoin d'une distribution uniforme ? Est-ce que la dégradation des perfs à cause des deux appels à Random.int est vraiment importante ? Si oui, pour quelles valeurs de n ? Je rappelle quand même ceci :

Étant un tout jeune débutant en Caml, j'ai quelques difficultés à programmer une fonction qui reverrait un vecteur d'entiers compris entre 0 et (n-1) où chacun n'apparaitrait qu'une fois et une seule.

Vous devinez où je veux en venir (et sans doute aussi le soupçon de mauvaise foi qui va avec)

Cordialement,
Cacophrène