# Kth permutation (Standard ML)

**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>>=funrr(0, _)=[]| rr(n, k)= kmodn :: rr(n-1, kdivn)

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>>=valdfr = foldr(fn(x, rs)=> x :: map(fnr => r +(ifx <= rthen1else0))rs)[]

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>>=funperm(xs, k)= map(fni => List.nth(xs, i))(dfr(rr(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>>=funpar rs = foldl op+ 0 rsmod2

<<kthperm.sml>>=radix representation direct representation from radix rep parity from radix rep generate permutation utility functions ; app print(List.tabulate(24,fnk => implode(perm(explode "perm", k))^ " " ^ Int.toString(par(rr(4, k)))^ "\n"));

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 |