On this page
Description
The permutations of {1, ..., n} in lexicographic order form a list of n! entries: 362,880 for n = 9, and 2.4 × 10^18 for n = 20. Generating them all to find the k-th one is hopeless beyond tiny n. The list has a rigid structure, though. It's grouped by first digit, then by second digit within each group, and every block has a known size. So the k-th permutation can be computed one digit at a time, and a permutation's rank can be computed the same way in reverse.
We'll go from simple to more technical:
- The pattern: divide by block sizes, (n - 1)!, (n - 2)!, ..., to pick each digit.
- A second flavor: the reverse, from a permutation to its rank.
- Where ranking and unranking are used (sampling, indexing orderings).
- What breaks it: off-by-one, overflow, and counting digits already used.
The approach
Java
String getPermutation(int n, int k) {
List<Integer> digits = new ArrayList<>(); // unused digits, in order
long[] factorial = new long[n + 1];
factorial[0] = 1;
for (int i = 1; i <= n; i++) { digits.add(i); factorial[i] = factorial[i - 1] * i; }
k--; // 1-indexed rank -> 0-indexed
StringBuilder result = new StringBuilder();
for (int position = n; position >= 1; position--) {
long block = factorial[position - 1]; // permutations sharing the next digit
int index = (int) (k / block); // which remaining digit comes next
k %= block; // rank within that block
result.append(digits.remove(index));
}
return result.toString();
}
Python
def get_permutation(n: int, k: int) -> str:
digits = list(range(1, n + 1)) # unused digits, in order
factorial = [1] * (n + 1)
for i in range(1, n + 1):
factorial[i] = factorial[i - 1] * i
k -= 1 # 1-indexed rank -> 0-indexed
result = []
for position in range(n, 0, -1):
block = factorial[position - 1] # permutations sharing the next digit
index, k = divmod(k, block) # which remaining digit comes next, and the rank within its block
result.append(str(digits.pop(index))) # pop by POSITION - list.remove() is by value
return "".join(result)
Fixing the first digit leaves (n - 1)! ways to arrange the rest, so the first (n - 1)! permutations start with the smallest digit, the next (n - 1)! with the second smallest, and so on. Dividing the 0-indexed rank by (n - 1)! picks the first digit; the remainder is the rank inside that block - the same problem with one digit fewer. For n = 4, k = 9: k - 1 = 8, 8 / 3! = 1, so the first digit is 2 (the second smallest), and the answer is 2314.
A second flavor: from permutation back to rank
The same blocks run backward. Every digit that is smaller than perm[i] and still unused could have started a whole earlier block of (n - 1 - i)! permutations:
Java
long rank = 0;
for (int i = 0; i < n; i++) {
int smallerUnused = 0;
for (int j = i + 1; j < n; j++) if (perm[j] < perm[i]) smallerUnused++; // still available at position i
rank += smallerUnused * factorial[n - 1 - i];
}
return rank + 1; // back to 1-indexed
Python
from math import factorial
def permutation_rank(perm: list[int]) -> int:
n, rank = len(perm), 0
for i in range(n):
smaller_unused = sum(1 for j in range(i + 1, n) if perm[j] < perm[i]) # still available at position i
rank += smaller_unused * factorial(n - 1 - i)
return rank + 1 # back to 1-indexed
For 3 5 1 4 2: 2 * 4! + 3 * 3! + 0 + 1 * 1! + 0 = 67, so it's the 68th permutation. Counting all smaller digits (perm[i] - 1) instead of the smaller unused ones overcounts, since digits already placed can't start a block - it gives 77.
Where you'll see it
Converting between a permutation and its rank (the factorial number system, or Lehmer code) lets a permutation be stored as one integer, lets test harnesses reproduce "the k-th ordering" from a seed, and lets search algorithms index permutation states compactly - for example, a table indexed by the rank of a puzzle's arrangement.
Which tool for which job?
| You need | Use |
|---|---|
| The k-th permutation | k--, then pick each digit by dividing by the block size |
| The rank of a permutation | add (smaller unused digits) × (block size) at each position |
| Both, for large n | a Fenwick tree over the unused digits: O(n log n) |
| Repeated elements | block sizes divided by the factorials of the multiplicities |
| A uniformly random permutation | Fisher-Yates shuffle |
| n above 20 in Java | BigInteger ranks |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Skipping k-- | n = 3, k = 3 gives 231 instead of 213 | work 0-indexed |
Factorials in int | 13! comes out as 1932053504 | long up to 20!, BigInteger beyond |
| Counting all smaller digits for the rank | 77 instead of 67 for 3 5 1 4 2 | count only the unused ones |
digits.remove(index) in Python | removes by value, not position | digits.pop(index) |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. For n = 4, how many permutations start with each digit, and what's the first digit of the 9th?
Show answer
3! = 6 each. Ranks 1-6 start with 1 and 7-12 start with 2, so the 9th starts with 2. In code: (9 - 1) / 6 = 1, the second smallest remaining digit.
2. What goes wrong if k isn't decremented first?
Show answer
The division treats k as 0-indexed, so every answer shifts one permutation later: n = 3, k = 3 gives 231 instead of 213. For k = n!, the first division returns n, one past the last remaining digit.
3. What is the rank of 3 5 1 4 2, and why count only unused smaller digits?
Show answer
- At each position, a smaller digit that's still available could have started an earlier block: 2 * 4! (for 1 and 2 before 3) + 3 * 3! + 0 + 1 * 1! + 0 = 67 earlier permutations. Digits already placed can't start a block at a later position, so counting them (
perm[i] - 1) overcounts - to 77.
Key takeaways
- Each choice of the next digit owns a block of (remaining - 1)! consecutive permutations.
- Unranking: convert k to 0-indexed, divide by the block size to pick the digit, keep the remainder.
- Ranking runs it backward: sum (smaller unused digits) * block size, then add 1.
- Use
longfactorials - fine up to n = 20; beyond that,BigInteger. - O(n^2) with a list (O(n log n) with a Fenwick tree) instead of O(n!).