Lexicographic enumeration, ranking and unranking of permutations of r out of n objects

Abstract

Let P(n,r) = {P _n , _r |P _n , _r = p ₁ p ₂…p _r and p ₁,p ₂,…,p _r ∊Z and p ₁≠p _j if i≠j}, where Z = {1,2,…,n}. An θ(r) algorithm for enumerating P(n,r) in the lexicographic order is presented. The mapping from P(n,r) to the set of their inversions and the inverse mapping are established by a pair of coding and decoding algorithms. Furthermore, ranking and unranking algorithms are also provided for establishing the mappings between P(n,r) and Z = {1,2,…,|P(n,r)|}. Indeed, the enumeration, ranking and unranking algorithms are more general than known algorithms.

Keywords:

• Permutations
• lexicographic order
• enumeration
• ranking
• unranking
• coding
• decoding

C.R. Categories:

• G.2.1
• F.2.2