Project Euler 24: Lexicographic Permutations
Peter Prevos |
558 words | 3 minutes
Share this content
Project Euler 24 asks to develop lexicographic permutations. These are ordered arrangements of objects in lexicographic order. Tushar Roy of Coding Made Simple has shared a great introduction on how to generate lexicographic permutations.
Project Euler 24 Definition
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
$$012 \quad 021 \quad 102 \quad 120 \quad 201 \quad 210$$
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
Proposed Solution
The digits 0 to 9 have $10! = 362880$ permutations (including combinations that start with 0). Most of these permutations are, however, not in lexicographic order. A brute-force way to solve the problem is to determine the next lexicographic permutation of a number string and repeat this one million times. This code takes the following steps:
- Find largest index $i$ such that$a_{i-1} < a_i$.
- If no such index exists, then this is already the last permutation.
- Find largest index $j$ such that $j \geq i$ and $a_j > a_{i-1}$.
- Swap $a_j$ and $a_{i-1}$.
- Reverse the suffix starting at $a_i$.
## Project Euler 24: Lexicographic permutations
nextPerm <- function(a) {
# Find longest non-increasing suffix
i <- length(a)
while (i > 1 && a[i - 1] >= a[i])
i <- i - 1
# i is the head index of the suffix
# Are we at the last permutation?
if (i <= 1) return (NA)
# a[i - 1] is the pivot
# Frind rightmost element that exceeds the pivot
j <- length(a)
while (a[j] <= a[i - 1])
j <- j - 1
# Swap pivot with j
temp <- a[i - 1]
a[i - 1] <- a[j]
a[j] <- temp
# Reverse the suffix
a[i:length(a)] <- rev(a[i:length(a)])
return(a)
}
numbers <- 0:9
for (i in 1:(1E6 - 1)) numbers <- nextPerm(numbers)
answer <- paste(numbers, collapse = "")
print(answer)Combinatorics
A more efficient solution is to use combinatorics, thanks to the now defunct MathBlog. The last nine digits can be ordered in 9! = 362880 ways. So the first 9! permutations start with a 0. By extending this thought, it follows that the millionth permutation must start with a 2.
$$\lfloor (1000000 - 1) / 9 ! \rfloor = 2$$
From this rule, it follows that the 725761st permutation is 2,013,456,789. We now need 274,239 more lexicographic permutations:
$$(1000000 - 1) - (2 \times 9!) = 274239$$
We can repeat this logic to find the next digit. The last 8 digits can be ordered in 40320 ways. The second digit is the 6th digit in the remaining numbers, which is 7 (2013456789).
$$\lfloor 274239 / 8 ! \rfloor = 6$$
$$274239 - (6 \times 7 !) = 32319$$
This process is repeated until all digits have been used.
numbers <- 0:9
n <- length(numbers)
answer <- vector(length = 10)
remain <- 1E6 - 1
for (i in 1:n) {
j <- floor(remain / factorial(n - i))
answer[i] <- numbers[j + 1]
remain <- remain %% factorial(n - i)
numbers <- numbers[-(j + 1)]
}
answer <- paste(answer, collapse = "")
print(answer)Share this content
