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

To leave a comment for the author, please follow the link and comment on his blog: Tony's bubble universe » R.

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



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

Tags: , ,

Comments are closed.