# Kth permutation (Python, functional)

### 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>>=rr =lambdan,k: (n > 0)and[k%n] + rr(n-1,k/n)or[]

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 =lambdars: len(rs)andrs[:1] + [r + (rs[0]<=r)forrindfr(rs[1:])]or[]

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 =lambdaxs,k: [xs[i]foriindfr(rr(len(xs),k))]

## wrapping up

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

<<parity from radix rep>>=par =lambdars: sum(rs)%2

<<kthperm.py>>=radix representation direct representation from radix rep parity from radix rep generate permutationif__name__ == "__main__":forkinrange(24):

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 |