Kth permutation (OCaml)

From LiteratePrograms

Other implementations: Haskell | OCaml | Python, functional | Standard ML

Generate any given permutation of a list. The number of distinct permutations is n! where n is the length of the input.

theory

We follow Iverson's recursive approach from his 1979 Turing Award lecture, — but in a language which may be a little more accessible than the original notation:

RR:1+(Φιω)τ_1+ι!ω
DFR:ω[1],X+ω[1]≤X←DFR 1↓ω:0=ρω:ω

practice

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>>=
radix representation
direct representation from radix rep
parity from radix rep
generate permutation
utility functions
;;
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.

Download code