# Kth permutation (Haskell)

**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>>=rr :: Int -> Int ->[Int]rr 0 _ =[]rr n k = k `mod` n : rr(n-1)(k `div` 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>>=dfr ::[Int]->[Int]dfr = foldr(\x rs -> x :[r +(ifx <= rthen1else0)| r <- 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>>=perm ::[a]-> Int ->[a]perm xs k =[xs !! i | 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>>=par ::[Int]-> Int par rs = sum rs `mod` 2

<<kthperm.hs>>=radix representation direct representation from radix rep parity from radix rep generate permutation main = mapM_(\k -> putStrLn(perm "perm" k ++ " " ++ show(par(rr 4 k))))[0..23]

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 |