(*factorielle*)
let fact n =
let rec f acc = function
| 0 -> acc
| n -> f (n*acc) (n-1)
in f 1 n;;
(*trouve la nth eme permutation des elements de la liste li, constituee de nbr elements*)
let rec perm nth nbr li=
let rec f nth nbr li = function
| [] -> li
|hd::lt ->
let fnbr=fact (nbr -1)
in if nth < fnbr then
hd:: (perm nth (nbr-1) (List.filter (fun x -> x <> hd) li))
else
f (nth - fnbr) nbr li lt
in f nth nbr li li;;
perm 999999 10 [0;1;2;3;4;5;6;7;8;9];;
Remarque :
exemple :
perm 999999 10 [0;1;2;3;4;5;6;7;8;9];;
=> 2783915460
les permutations lexicographiques de [0;1;2] sont (dans l'ordre) :
[0; 1; 2]
[0; 2; 1]
[1; 0; 2]
[1; 2; 0]
[2; 0; 1]
[2; 1; 0]
pour une liste de taille n, il y en a n!, elles sont triees selon la position des elements dans la liste de depart.