# Kth permutation (Python, functional)

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

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))]

## [edit] 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:

abcd 0 bacd 1 cabd 0 dabc 1 acbd 1 bcad 0 cbad 1 dbac 0 adbc 0 bdac 1 cdab 0 dcab 1 abdc 1 badc 0 cadb 1 dacb 0 acdb 0 bcda 1 cbda 0 dbca 1 adcb 1 bdca 0 cdba 1 dcba 0

*Exercise: modify the loop above to generate the same permutations, but in a pseudo-random order*.

Download code |