# Lexicographic Permutations: Euler Problem 24

June 14, 2017
By

(This article was first published on The Devil is in the Data, and kindly contributed to R-bloggers)

Euler Problem 24 asks to develop lexicographic permutations which 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.

## Euler Problem 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 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

## Brute Force Solution

The digits 0 to 9 have $10! = 3628800$ 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.

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
# Find 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)


This code takes the following steps:

1. Find largest index $i$ such that $a_{i-1} < a_i$.
1. If no such index exists, then this is already the last permutation.
2. Find largest index $j$ such that $j \geq i$ and
3. Swap $a_j$ and $a_{i-1}$.
4. Reverse the suffix starting at $a_i$.

## Combinatorics

A more efficient solution is to use combinatorics, thanks to 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 2013456789. We now need 274239 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)]
}


R blogger Tony’s Bubble Universe created a generalised function to solve this problem a few years ago.

The post Lexicographic Permutations: Euler Problem 24 appeared first on The Devil is in the Data.

To leave a comment for the author, please follow the link and comment on their blog: The Devil is in the Data.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...