Chapter 38

Permutations

38.1 The universal sequence of permutations

For convenient programming we seek an enumeration of the permuta-
tions. Regard each permutation of 1, 2,.. .nas a bijectionπ:N→N
which is “eventually” constant,i.e.,f(m)=mform>n. The enu-
meration begins with the identity permutation. The permutations of 1,
2, ...nare among the firstn!of them, and each of the first(n−1)!
permutations ends withn.

Given an integerm, we write

m−1=r 2 ×1! +r 3 ×2! +···+rk×(k−1)!

for 0 ≤ri<i. These can be calculated recursively as follows. Begin-
ning with(q 1 ,r 1 )=(m− 1 ,0), we set, for eachi≥ 2 ,

qi− 1 =i×qi+ri.

In other words,

(qi,ri)=

(⌊q

i− 1

i

⌋

, mod(qi− 1 ,i)

)

.

Along with these, we construct a sequence of lists which ends at the
desired permutation. LetL 1 =(1).Fori≥ 2 , formLiby insertingi
intoLi− 1 so that there are exactlyrimembers smaller thanion its right
hand side. ThenLkis the permutation corresponding tom.