Set A is a finite totally ordered set of symbols. Because set A is finite and totally ordered, it's well-ordered. So, I'll just say A = {1, 2, ..., n} for some n. (1, 2, ..., n) is a finite n-long sequence over A. Consider its set of permutations and the lexicographic order over it. What's the kth permutation with respect to the order?
Notice that there's n! many n-permutations and (n-1)! many n-permutations that begin with a chosen first number. For example, there are (n-1)! n-permutations that are of form (1, ...) and (n-1)! n-permutations that are of form (2, ...) and (n-1)! n-permutations that are of form (3, ...) and so on. So, the corresponding number for the first permutation of form (x, ...) is immediately apparent.
Let k = k' + 1
k' = 0 for (
1,2,3, ..., n)
k' = (n - 1)! for (
2, 1, 3, ..., n)
k' = 2(n - 1)! for (
3, 1, 2, ..., n)
...
k' = (n - 1)(n - 1)! for (n, 2, 3, ..., n-1)
So, if a sequence is of form (x,...), then it's number is greater than or equal to (x-1)(n-1)!
What then can we say about sequences of form (x,y, ...), x≠y? Is there a numbering for the pairs (x,y), x≠y for which I can make a similar bound? First, observe that there are n(n-1) = nP2 such pairs.
remark
The obvious intuition for nP2 is that by choosing one element and then another without replacement, there's n(n - 1) choices: nP2 = (n choose 1)(n-1 choose 1) = n(n - 1).
Here's a way to think about nP2 without the idea of "choosing": consider the set of all pairs A✕A. There's n2 many of those pairs. And, there's n of those pairs (x,y) in which x=y. so there's n2-n = n(n-1) pairs in A✕A - {(1,1), (2,2), ..., (n,n)}. That corresponds to choosing a pair without replacement. A geometric way to think of this is to consider how many cells are in an "n by n" grid minus the diagonal.
Observe that the set of permutations of the sequence (1,2, ..., n) is also the set of all n-long sequences whose elements are distinct. Notice, that this means that elements of a permutation sequence s are coupled by the following constraint/sentence: for all i and j in [1,n], if i ≠ j, then s(i) ≠ s(j). An interesting consequence of this coupling is that if you pick all other n-1 elements of the sequence the final element is fully determined.
This coupled-ness makes finding a desired numbering over the original permutation sequence very inconvenient. Consider the first sequence of form (2,1, ...) and the first sequence of form (2, 3, ...). The first sequences' corresponding number is (n - 1)(n - 2)!=(n - 1)!, but the second's corresponding number is n(n - 2)! . Finding this numbering would involve numbering the pairs A✕A - {(1,1), (2,2), ..., (n,n)} lexicographically, so the numberings for sequences (x, x - 1, ...) and (x, x + 1, ...) have to be adjacent by a factor of (n - 2)! .
second remark
Permutations with more inversions have a higher number. Can you characterize the of permutations with k exactly inversions? What about permutations with less than or equal to k inversions? What happens to a permutation's number when a swap is performed?
Still, there's an easy way to construct the desired correspondence between the n-permutations and [1, n!]. Naturally, it involves an intermediate sequence whose elements are decoupled.
First, I'll introduce a cool concept: the minimum excluded value. Say that S is a subset of a well-ordered set A. mex(S) is the minimum excluded value, i.e. the smallest value that is in A, but not in S. Here's a generalization: the kth smallest excluded value, which is the kth smallest value that is in A: kex(k,S). Notice that kex(1,S) = mex(S). Also, notice that kex(k, {1, ..., n}) = k.
One way to construct an n-permutation s1 is to
choose s1(0) by drawing the s2(0)th element from A = {1, ..., n},
and then choose s1(1) by drawing the s2(1)th element from A - {s1(0)},
and then choose s1(2) by drawing the s2(2)th element from A - {s1(0), s1(1)},
and so on.
The relation between s1 and s2 can be expressed neatly with kex:
s1(i) = kex( s2(i), A - {s1(0), ..., s1(i - 1)} )
Notice that the elements of this "picking sequence" s2 are decoupled, unlike the permutation sequence s1. Also, notice that s2(i) ∈ {1, 2, ..., n - i}. The decoupled-ness permits an easy numbering:
k' = (s2(0) - 1)(n - 1)! + ... + (s2(n - 1) - 1)0!
if s2'(i) = (s2(i)-1), then
k' = s2'(0)(n - 1)! + ... + s2'(n - 1)0!
This is a decomposition into a factorial numeral system, and the digits can be retrieved with division.
Here's accompanying Kotlin code
fun getPermutation(n: Int, k: Int): String {
val _factorial : MutableList<Int> = MutableList(n) {0}
_factorial[0] = 1
for (i in 1..(n-1)) {
_factorial[i] = _factorial[i-1] * i
}
val factorial : List<Int> = _factorial as List<Int>
val permutation = StringBuilder()
val picks : MutableList<Int> = mutableListOf<Int>()
for (i in 1..n) {
picks.add(i)
}
var kMinusOne : Int = k - 1 // k' is kMinusOne
for (i in 1..n) {
val s : Int = kMinusOne / factorial[n - i]
kMinusOne = kMinusOne % factorial[n-i]
permutation.append(picks[s])
picks.removeAt(s)
}
return permutation.toString()
}
Related:
Cantor expansion
mixed-radix numeral systems, factorial number systems
Minimum excluded value (mex)
kth order statistics
Lehmer codes