Kth permutation (OCaml)
Generate any given permutation of a list. The number of distinct permutations is n! where n is the length of the input.
RR:1+(Φιω)τ_1+ι!ω DFR:ω,X+ω≤X←DFR 1↓ω:0=ρω:ω
The radix representation, rr, takes advantage of the 1-1 correspondence between and the permutations of sequences of length n.
- for sequences of length 0, there is only one possible choice
- for a sequence of length n, there are n possible choices, then n-1 after that. k can thus be unfolded as a sequence of radices, much like a value can be unfolded as a sequence of digits in a given base, but in this case the base varies
Exercise: Iverson uses APL's τ base representation operator to generate permutations in lexicographic order. Alter this definition to do the same.
<<radix representation>>= let rec rr n k = if n = 0 then  else k mod n :: rr (n-1) (k / n)
In the radix representation, each choice is represented as an index into the list of remaining possibilities. dfr converts these indices to indices into the original list, by concatenating each choice with the conversion of the remaining possibilities — and incrementing all of the indices that come after the chosen element.
Question: how close is this process to the reverse of Selection sort (Python, arrays)?
<<direct representation from radix rep>>= let dfr xs = List.fold_right (fun x rs -> x :: List.map (fun r -> r + (if x <= r then 1 else 0)) rs) xs 
To generate the requested permutation, perm, we take the kth radix rep. with rr, convert it with dfr, then directly select elements of the original alphabet.
<<generate permutation>>= let perm xs k = List.map (List.nth xs) (dfr (rr (List.length xs) k))
 wrapping up
Finally, we provide a rudimentary test: print each anagram of “perm”, along with its parity,
<<parity from radix rep>>= let par rs = List.fold_left (+) 0 rs mod 2
We provide utility functions to convert between strings and lists of characters:
<<utility functions>>= let list_of_string str = let result = ref  in String.iter (fun x -> result := x :: !result) str; List.rev !result let string_of_list lst = let result = String.create (List.length lst) in ignore (List.fold_left (fun i x -> result.[i] <- x; i+1) 0 lst); result
<<kthperm.ml>>= ;; for k = 0 to 23 do Printf.printf "%s %d\n" (string_of_list (perm (list_of_string "perm") k)) (par (rr 4 k)) done;;
to produce the following output:
perm 0 eprm 1 rpem 0 mper 1 prem 1 erpm 0 repm 1 mepr 0 pmer 0 empr 1 rmpe 0 mrpe 1 pemr 1 epmr 0 rpme 1 mpre 0 prme 0 ermp 1 remp 0 merp 1 pmre 1 emrp 0 rmep 1 mrep 0
Exercise: modify the loop above to generate the same permutations, but in a pseudo-random order.