# Project Euler — problem 24

November 20, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

It’s a lovely day. I took a walk around the campus after lunch. The scene was enjoyable in one deep autumn day. Before the afternoon work, I’d like to spend a few moments on the 24th Euler Problem.

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?

First of all, how many lexicographic permutations of the digits 0-9? Obviously, it’s 10*9*8*…*1, which is 10! = 3628800. One million is indeed within this range. So let’s find it out. (Here, I came up with a better solution to calculate each digit directly.)

Hint: There are 9! = 362880 permutations with 0 at the first digit so the first digit is not going to be 0 for the millionth. The next 362880 permutations start with 1′s. So it won’t be 1 either. And the 725761st-1088640th, in which lies in the millionth, start with 2′s. So the first digit of millionth is 2. Well, hope my solution is well understood. Here’s the code.

?View Code RSPLUS
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  num.seq <- 0:9 n <- 1e6 Lexico <- function(num.seq, n) { len <- length(num.seq) if (n > prod(1:len) | n < 1) { print("Error. The number required is beyond.") } else { nth <- numeric(len) for (i in 1:(len - 1)) { if (n == 0) { nth[i] <- num.seq[length(num.seq)] } else { tmp <- prod(1:(len - i)) div <- floor((n - 1) / tmp) nth[i] <- num.seq[div + 1] } n <- n %% tmp num.seq <- num.seq[num.seq != nth[i]] } nth[len] <- num.seq return(nth) } } cat("The result is:", Lexico(num.seq, n), "\n")

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