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 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) answer <- numbers print(answer)

This code takes the following steps:

- Find largest index such that .
- If no such index exists, then this is already the last permutation.

- Find largest index such that and .
- Swap and .
- Reverse the suffix starting at .

## Combinatorics

A more efficient solution is to use combinatorics, thanks to MathBlog. The last nine digits can be ordered in ways. So the first permutations start with a 0. By extending this thought, it follows that the millionth permutation must start with a 2.

From this rule, it follows that the 725761^{st} permutation is 2013456789. We now need 274239 more lexicographic permutations:

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).

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)

View the latest version of this code on GitHub.

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

Pingback: Lexicographic Permutations: Euler Problem 24 | A bunch of data

Pingback: Lexicographic Permutations: Euler Problem 24 – Mubashir Qasim

Nice description!

I made a program (using visual basic) that allow to calculates the index of a given permutation or viceversa (it calculates the permutation by the index).

You can use the program (also for testing your works).

The link to the program page is :

http://lotterie.xoom.it/virgiliowizard/factorindex-1-0-english?SESSb5056350d5fafc537641133bcfbe593a=fb7da79df37f33899b3aea4de3a9be0e

Thanks Stepano, perhaps I could develop a generalised function in R.