Kth permutation (Haskell)
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>>= 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 + (if x <= r then 1 else 0) | 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)]
 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>>= 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.