9.5
Idea: write k − 1 in the factorial number system (mixed-radix).
If
[math]\displaystyle{k-1=\sum_{i=1}^{n}(d_i\,(n-i)!)}[/math] with [math]0\le d_i\le n-i[/math], then the digits d₁ d₂ … dₙ tell how many unused elements to skip when choosing the next symbol of the permutation.
Algorithm (1-indexed k):
PERMUTE(n,k)
A ← [1,2,…,n] ⟵ remaining symbols
k ← k−1 ⟵ change to 0-based rank
for i ← 1 to n
f ← (n−i)! ⟵ block size
idx ← ⌊k / f⌋ ⟵ which block
output A[idx] ⟵ pick that symbol
delete A[idx] ⟵ remove it
k ← k mod f
Complexity: deleting from a plain list costs [math]O(n^2)[/math]; using a balanced tree/Fenwick tree turns it into [math]O(n\log n)[/math]. Space is [math]O(n)[/math].
Tiny Python reference implementation:
from math import factorial
def kth_perm(n, k):
k -= 1
avail = list(range(1, n+1))
perm = []
for i in range(n, 0, -1):
f = factorial(i-1)
idx, k = divmod(k, f)
perm.append(avail.pop(idx))
return perm
The routine directly produces the required permutation without enumerating the first [math]k-1[/math] permutations.
Back to
Chapter 9
