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.