# Kth permutation (OCaml)

**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.

## [edit] theory

We follow Iverson's recursive approach from his 1979 Turing Award lecture, *Notation as a Tool of Thought* — 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=ρω:ω

## [edit] 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>>=letrecrr n k =ifn = 0then[]elsekmodn :: 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>>=letdfr xs = List.fold_right(funx rs -> x :: List.map(funr -> r +(ifx <= rthen1else0))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>>=letperm xs k = List.map(List.nth xs)(dfr(rr(List.length xs)k))

## [edit] wrapping up

Finally, we provide a rudimentary test: print each anagram of “perm”, along with its parity,

<<parity from radix rep>>=letpar rs = List.fold_left(+)0 rsmod2

We provide utility functions to convert between strings and lists of characters:

<<utility functions>>=letlist_of_string str =letresult = ref[]inString.iter(funx -> result := x :: !result)str; List.rev !resultletstring_of_list lst =letresult = String.create(List.length lst)inignore(List.fold_left(funi 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 ;;fork = 0to23doPrintf.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 |